Lua의 재귀
재귀 알고리즘을 구현하고 Lua의 꼬리 호출 최적화를 이해합니다.
Lua의 재귀은(는) CoddyKit의 무료 Lua Academy 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Lua Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Lua Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
재귀란 무엇인가요?
재귀란 함수가 같은 문제의 더 작은 사례를 해결하기 위해 자기 자신을 호출하는 것입니다. 모든 재귀 함수에는 중단 지점인 기본 사례와 문제를 줄이는 재귀 사례가 필요합니다. 기본 사례가 없으면 재귀로 인해 스택 오버플로가 발생합니다.
local function countdown(n)
if n <= 0 then
print("Blast off!")
return
end
print(n)
countdown(n - 1)
end
countdown(5)
-- 5, 4, 3, 2, 1, Blast off!팩토리얼
팩토리얼은 대표적인 재귀 예제입니다: n! = n × (n-1)!이며 기본 사례는 0! = 1입니다. 각 호출은 기본 사례에 도달할 때까지 n을 1씩 줄입니다. 결과는 호출 스택을 따라 되돌아오며 그 과정에서 곱셈이 이루어집니다.
local function factorial(n)
if n <= 1 then return 1 end
return n * factorial(n - 1)
end
print(factorial(1)) -- 1
print(factorial(5)) -- 120
print(factorial(10)) -- 3628800피보나치
피보나치 수열도 대표적인 예제입니다: fib(n) = fib(n-1) + fib(n-2). 단순한 재귀는 같은 값을 반복해서 다시 계산하므로 지수 시간이 걸립니다. 이를 해결하는 메모이제이션을 살펴보겠지만, 먼저 기본 형태부터 보겠습니다.
local function fib(n)
if n <= 1 then return n end
return fib(n - 1) + fib(n - 2)
end
for i = 0, 10 do
io.write(fib(i) .. " ")
end
print()
-- 0 1 1 2 3 5 8 13 21 34 55메모이제이션 재귀
메모이제이션은 이미 계산한 결과를 테이블에 저장합니다. 호출할 때마다 먼저 저장된 값을 확인합니다. 값이 있으면 즉시 반환하고, 없으면 계산한 뒤 저장합니다. 이렇게 하면 피보나치의 지수 시간이 선형 시간으로 바뀝니다.
local memo = {}
local function fib(n)
if memo[n] then return memo[n] end
if n <= 1 then return n end
local result = fib(n-1) + fib(n-2)
memo[n] = result
return result
end
print(fib(40)) -- 102334155 (fast!)꼬리 호출 최적화
Lua는 꼬리 호출 최적화(TCO)를 수행합니다. 함수의 마지막 동작이 다른 함수 호출일 때 Lua는 현재 스택 프레임을 재사용합니다. 따라서 꼬리 재귀 함수는 O(1)의 스택 공간만 사용합니다. 모든 재귀가 꼬리 재귀인 것은 아닙니다. 호출이 함수에서 마지막 동작이어야 합니다.
-- Tail-recursive factorial using accumulator
local function factTail(n, acc)
acc = acc or 1
if n <= 1 then return acc end
return factTail(n - 1, n * acc) -- tail call
end
print(factTail(10)) -- 3628800
-- Can handle very large n without stack overflow트리 순회
재귀는 트리 순회를 자연스럽게 표현합니다. 트리는 value, left, right 필드를 가진 테이블입니다. 전위, 중위, 후위 순회는 재귀 호출 전후 중 언제 값을 처리하는지만 다릅니다.
local function inorder(node)
if node == nil then return end
inorder(node.left)
io.write(node.value .. " ")
inorder(node.right)
end
local tree = {
value=4,
left={value=2, left={value=1}, right={value=3}},
right={value=6, left={value=5}, right={value=7}}
}
inorder(tree) -- 1 2 3 4 5 6 7상호 재귀
두 함수는 서로를 호출할 수 있습니다(상호 재귀). Lua에서는 전방 선언이 필요합니다. 먼저 로컬 변수를 선언한 다음 함수를 할당합니다. 이렇게 하면 각 함수가 이미 범위 안에 있는 다른 함수의 변수를 참조할 수 있습니다.
local isEven, isOdd
isEven = function(n)
if n == 0 then return true end
return isOdd(n - 1)
end
isOdd = function(n)
if n == 0 then return false end
return isEven(n - 1)
end
print(isEven(10)) -- true
print(isOdd(7)) -- true재귀적 깊은 복사
재귀는 중첩된 구조를 처리하는 데 적합합니다. 테이블을 깊은 복사한다는 것은 그 내용을 복사하고 중첩된 테이블도 재귀적으로 복사하는 것을 의미합니다. 따라서 복사본을 수정해도 원본에는 영향을 주지 않습니다.
local function deepCopy(orig)
local copy
if type(orig) == "table" then
copy = {}
for k, v in pairs(orig) do
copy[deepCopy(k)] = deepCopy(v)
end
setmetatable(copy, getmetatable(orig))
else
copy = orig
end
return copy
end
local a = {1, {2, 3}}
local b = deepCopy(a)
b[2][1] = 99
print(a[2][1]) -- 2 (unchanged)플러드 필 알고리즘
플러드 필(그림판 프로그램과 게임 맵에서 사용됨)은 자연스럽게 재귀로 구현됩니다. 한 칸에서 시작해 해당 칸을 표시한 다음 방문하지 않은 각 이웃을 재귀적으로 채웁니다. 경계나 이미 방문한 칸에 도달하면 재귀가 종료됩니다.
local grid = {
{0,0,0,1,0},
{0,1,0,1,0},
{0,1,1,1,0},
{0,0,0,0,0},
}
local function fill(g, r, c)
if r<1 or r>#g or c<1 or c>#g[r] then return end
if g[r][c] ~= 0 then return end
g[r][c] = 2 -- mark visited
fill(g,r-1,c); fill(g,r+1,c)
fill(g,r,c-1); fill(g,r,c+1)
end
fill(grid, 1, 1)
print(grid[1][1], grid[2][1]) -- 2 2스택 깊이 인식
Lua의 기본 호출 스택은 제한되어 있습니다(꼬리 호출이 아닌 호출은 일반적으로 약 200단계). 깊은 비꼬리 재귀는 "stack overflow" 오류를 일으킵니다. 해결 방법으로 꼬리 재귀로 변환하거나 명시적인 스택(테이블)을 사용하거나, 큰 반복 작업에는 코루틴을 사용할 수 있습니다.
-- Simulate deep recursion danger
local function depth(n)
if n == 0 then return "done" end
return depth(n - 1) -- tail call, safe
end
print(depth(100000)) -- done (tail call, no overflow)
-- Non-tail: limited depth
local function countDown(n)
if n == 0 then return 0 end
return 1 + countDown(n - 1) -- NOT a tail call
end
-- countDown(10000) would stack overflow빠른 확인
다음 중 Lua에서 올바른 꼬리 호출은 무엇일까요?
복습: 재귀
요약:
- 모든 재귀 함수에는 기본 사례와 재귀 사례가 필요합니다
- 꼬리 호출(마지막 동작이 호출인 경우)은 Lua에서 최적화되어 O(1) 스택을 사용합니다
- 메모이제이션은 지수 시간 재귀를 선형 시간으로 바꿉니다
- 상호 재귀에는 전방 선언이 필요합니다
- 트리나 그래프의 깊은 재귀는 자연스럽지만 비꼬리 호출에서는 스택 깊이에 주의해야 합니다
자주 묻는 질문
“Lua의 재귀” 강의는 무료인가요?
네 — “Lua의 재귀” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Lua Academy 강의 전체를 잠금 해제할 수 있습니다. Lua Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“Lua의 재귀”에서 뭘 배우나요?
재귀 알고리즘을 구현하고 Lua의 꼬리 호출 최적화를 이해합니다. 브라우저에서 직접 실행하는 실습 코드로 Lua Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Lua Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Lua Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.
“Lua의 재귀” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Lua Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Lua Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.