왜 재귀를 배워야 할까
반복문은 같은 일을 여러 번 처리할 때 강력합니다. 배열을 처음부터 끝까지 훑거나, 정해진 횟수만큼 계산할 때는 반복문이 가장 자연스럽습니다.
하지만 어떤 문제는 "같은 모양의 더 작은 문제"로 나누어 생각할 때 훨씬 단순해집니다. 예를 들어 폴더 안에 폴더가 있고, 그 안에 또 폴더가 있는 구조를 생각해 봅시다. 전체 파일 개수를 세려면 현재 폴더의 파일을 세고, 안쪽 폴더에 대해서도 똑같은 일을 하면 됩니다.
이처럼 문제 안에 같은 형태의 작은 문제가 들어 있을 때 재귀가 유용합니다.
재귀 함수는 쉽게 말해 자기 자신을 다시 호출하는 함수입니다. 정확히는, 어떤 함수가 문제를 해결하는 과정에서 자기 자신을 더 작은 입력으로 호출하는 구조를 말합니다.
러시아 인형을 떠올려 봅시다. 큰 인형을 열면 그 안에 작은 인형이 있고, 또 그 안에 더 작은 인형이 있습니다. 재귀도 비슷합니다. 큰 문제를 열면 같은 모양의 작은 문제가 나오고, 그 문제를 다시 열면 더 작은 문제가 나옵니다.
계단 오르기도 좋은 예입니다. 5번째 계단까지 가는 일을 생각해 봅시다. 마지막에 5번째 계단에 도착하려면, 먼저 4번째 계단까지 올라간 뒤 한 칸 더 오르면 됩니다.
5번째 계단까지 오르기
= 4번째 계단까지 오르기 + 한 칸 오르기
4번째 계단까지 오르기
= 3번째 계단까지 오르기 + 한 칸 오르기이런 식으로 문제를 계속 줄이다 보면 더 이상 줄일 필요가 없는 가장 작은 상황에 도착합니다. 재귀에서는 이 지점을 특히 중요하게 다룹니다.
AI 생성 이미지
재귀 함수의 기본 구조
재귀 함수에는 반드시 두 부분이 필요합니다.
첫째, 종료 조건입니다. 더 이상 자기 자신을 호출하지 않고 답을 바로 반환하는 경우입니다.
둘째, 재귀 호출입니다. 원래 문제보다 작은 문제를 만들고, 같은 함수를 다시 호출하는 부분입니다.
기본 형태는 다음과 같습니다.
function solve(problem):
if problem이 충분히 작다:
return 바로 구할 수 있는 답
smaller_problem = problem을 작게 만든 것
return solve(smaller_problem)을 이용한 답종료 조건이 없으면 함수는 멈추지 않습니다.
function bad(n):
print(n)
bad(n - 1)위 함수는 n이 0이 되어도, 음수가 되어도 계속 자기 자신을 부릅니다. 이런 상황을 무한 호출이라고 합니다. 실제 프로그램에서는 함수 호출이 계속 쌓이다가 더 이상 저장할 공간이 없어 오류가 발생합니다.
여기서 등장하는 개념이 호출 스택입니다. 호출 스택은 아직 끝나지 않은 함수 호출을 차곡차곡 쌓아 두는 공간입니다. 함수가 다른 함수를 호출하면 새 호출이 위에 쌓이고, 함수가 끝나면 맨 위 호출이 사라집니다.
재귀에서는 자기 자신을 부르므로 호출 스택에 같은 함수가 여러 번 쌓입니다.
count(3)
count(2)
count(1)
count(0)count(0)이 끝나야 count(1)이 끝나고, 그다음 count(2), count(3)이 차례로 끝납니다. 재귀를 이해할 때는 "함수가 호출된다"뿐 아니라 "끝나지 않은 호출이 쌓여 있다"는 점을 함께 생각해야 합니다.
팩토리얼로 보는 재귀 흐름
팩토리얼은 재귀를 배우기 좋은 대표 예제입니다. n!은 1부터 n까지의 곱입니다.
5! = 5 × 4 × 3 × 2 × 1이 식은 다음처럼 바꿀 수 있습니다.
5! = 5 × 4!
4! = 4 × 3!
3! = 3 × 2!즉, n!은 n × (n - 1)!입니다. 같은 형태의 더 작은 문제가 보입니다.
종료 조건은 1! = 1 또는 0! = 1로 둘 수 있습니다. 여기서는 n == 0일 때 1을 반환하겠습니다.
function factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)factorial(4)의 흐름을 손으로 따라가 봅시다.
factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * (3 * (2 * (1 * factorial(0))))
= 4 * (3 * (2 * (1 * 1)))
= 24처음에는 호출이 안쪽으로 깊어집니다. 종료 조건을 만나면 그때부터 결과가 바깥쪽으로 돌아오며 계산됩니다.
재귀를 처음 볼 때 헷갈리는 이유는 계산이 한 방향으로만 진행되지 않기 때문입니다. 먼저 작은 문제로 내려가고, 그다음 답을 가지고 올라옵니다.
피보나치 수열과 중복 호출
피보나치 수열은 앞의 두 수를 더해 다음 수를 만드는 수열입니다.
0, 1, 1, 2, 3, 5, 8, 13, ...정의는 다음과 같습니다.
fib(0) = 0
fib(1) = 1
fib(n) = fib(n - 1) + fib(n - 2)이를 그대로 재귀 함수로 쓰면 다음과 같습니다.
function fib(n):
if n == 0:
return 0
if n == 1:
return 1
return fib(n - 1) + fib(n - 2)fib(5)를 호출하면 다음과 같은 구조가 생깁니다.
fib(5)
= fib(4) + fib(3)
= (fib(3) + fib(2)) + (fib(2) + fib(1))여기서 fib(3)과 fib(2)가 여러 번 등장합니다. 같은 값을 반복해서 계산하는 것입니다.
이 예제는 중요한 사실을 알려 줍니다. 재귀로 표현하기 쉽다고 해서 항상 효율적인 것은 아닙니다. 피보나치의 단순 재귀 풀이는 중복 호출이 많아 입력이 커지면 매우 느려집니다.
하지만 지금 단계에서 더 중요한 것은 구조를 읽는 능력입니다.
종료 조건은 무엇인가?
더 작은 문제는 무엇인가?
작은 문제들의 답을 어떻게 합치는가?
이 세 질문을 던지면 재귀 코드를 훨씬 안정적으로 이해할 수 있습니다. 중복 계산을 줄이는 방법은 뒤의 동적 계획법에서 다시 다룹니다.
배열 합 구하기: 반복문과 재귀 비교
배열의 합은 반복문으로 쉽게 구할 수 있습니다.
function sum_array(arr):
total = 0
for x in arr:
total = total + x
return total재귀로도 표현할 수 있습니다. 핵심은 "배열 전체의 합"을 "첫 번째 값 + 나머지 배열의 합"으로 보는 것입니다.
[3, 5, 2, 4]의 합
= 3 + [5, 2, 4]의 합
= 3 + 5 + [2, 4]의 합
= 3 + 5 + 2 + [4]의 합
= 3 + 5 + 2 + 4 + []의 합빈 배열의 합은 0입니다. 이것이 종료 조건입니다.
function sum_from(arr, index):
if index == length(arr):
return 0
return arr[index] + sum_from(arr, index + 1)예를 들어 arr = [3, 5, 2]라면 다음처럼 진행됩니다.
sum_from(arr, 0)
= 3 + sum_from(arr, 1)
= 3 + 5 + sum_from(arr, 2)
= 3 + 5 + 2 + sum_from(arr, 3)
= 3 + 5 + 2 + 0
= 10이 문제만 보면 반복문이 더 단순합니다. 그래서 모든 문제를 재귀로 바꿀 필요는 없습니다. 재귀는 도구입니다. 특히 문제의 구조가 자연스럽게 "작은 같은 문제"로 나뉠 때 쓰기 좋습니다.
분할 정복: 나누고, 풀고, 합친다
재귀가 한 방향으로 문제를 조금씩 줄이는 방식이라면, 분할 정복은 큰 문제를 여러 개의 작은 문제로 나누어 푸는 사고 방식입니다.
분할 정복은 보통 세 단계로 진행됩니다.
분할: 큰 문제를 작은 문제들로 나눈다.
정복: 작은 문제들을 각각 해결한다.
결합: 작은 문제의 답을 모아 전체 답을 만든다.
정렬 단원에서 본 병합 정렬이 대표적인 분할 정복 알고리즘입니다.
병합 정렬은 배열을 반으로 나누고, 왼쪽과 오른쪽을 각각 정렬한 뒤, 두 정렬된 배열을 하나로 합칩니다.
[6, 2, 8, 3]
나누기:
[6, 2]와 [8, 3]
다시 나누기:
[6], [2], [8], [3]
각각은 원소가 하나이므로 이미 정렬됨
합치기:
[6] + [2] -> [2, 6]
[8] + [3] -> [3, 8]
[2, 6] + [3, 8] -> [2, 3, 6, 8]의사코드로 쓰면 다음과 같습니다.
function merge_sort(arr):
if length(arr) <= 1:
return arr
mid = length(arr) // 2
left = merge_sort(arr[0:mid])
right = merge_sort(arr[mid:length(arr)])
return merge(left, right)여기서 종료 조건은 배열의 길이가 1 이하일 때입니다. 원소가 0개이거나 1개인 배열은 더 정렬할 필요가 없습니다.
merge 함수는 이미 정렬된 두 배열을 앞에서부터 비교하며 작은 값을 차례대로 넣습니다.
function merge(left, right):
result = []
i = 0
j = 0
while i < length(left) and j < length(right):
if left[i] <= right[j]:
result.append(left[i])
i = i + 1
else:
result.append(right[j])
j = j + 1
남은 원소들을 result에 추가한다
return result병합 정렬의 강점은 나눌 때마다 문제 크기가 절반으로 줄어든다는 점입니다. 한 단계에서 전체 원소를 합치는 데 O(n)이 걸리고, 나누는 깊이는 O(log n)입니다. 그래서 전체 시간 복잡도는 O(n log n)이 됩니다.
재귀 문제를 생각하는 순서
재귀 코드를 바로 쓰려고 하면 어렵습니다. 다음 순서로 생각하면 부담이 줄어듭니다.
먼저, 함수가 무엇을 반환해야 하는지 한 문장으로 정합니다.
factorial(n)은 n!을 반환한다.
fib(n)은 n번째 피보나치 수를 반환한다.
sum_from(arr, index)는 index부터 끝까지의 합을 반환한다.그다음 가장 작은 입력에서 답이 무엇인지 정합니다. 이것이 종료 조건입니다.
factorial(0) = 1
fib(0) = 0, fib(1) = 1
index가 배열 길이와 같으면 합은 0마지막으로 원래 문제를 더 작은 문제로 바꿉니다.
factorial(n) = n * factorial(n - 1)
fib(n) = fib(n - 1) + fib(n - 2)
sum_from(arr, index) = arr[index] + sum_from(arr, index + 1)이 세 가지가 명확하면 재귀 함수의 뼈대는 거의 완성됩니다.
자주 틀리는 부분
가장 흔한 실수는 종료 조건을 빠뜨리는 것입니다. 재귀 함수에는 반드시 멈추는 지점이 있어야 합니다. 종료 조건이 틀리면 무한 호출이 발생하거나, 배열 범위를 벗어나는 오류가 생깁니다.
두 번째는 입력이 줄어들지 않는 재귀 호출입니다.
function wrong(n):
if n == 0:
return 0
return wrong(n)종료 조건이 있어도 n이 변하지 않으므로 절대 0에 가까워지지 않습니다. 재귀 호출에서는 입력이 종료 조건을 향해 움직여야 합니다.
세 번째는 반환값을 잊는 것입니다.
function factorial(n):
if n == 0:
return 1
factorial(n - 1) // 결과를 사용하지 않음재귀 호출의 결과를 받아서 현재 단계의 계산에 사용해야 합니다.
return n * factorial(n - 1)네 번째는 재귀가 항상 빠르다고 생각하는 것입니다. 피보나치처럼 같은 계산이 반복되면 매우 느릴 수 있습니다. 재귀는 표현을 단순하게 해 주는 도구이지, 자동으로 효율을 보장하는 방법은 아닙니다.
재귀를 볼 때는 겁내지 말고 세 가지만 확인하면 됩니다.
언제 멈추는가?
어떤 더 작은 문제를 푸는가?
작은 문제의 답으로 현재 답을 어떻게 만드는가?
이 질문에 답할 수 있다면 재귀 함수와 분할 정복은 더 이상 낯선 기법이 아닙니다. 큰 문제를 한 번에 해결하려 하지 않고, 작고 같은 모양의 문제로 나누어 해결하는 사고 방식입니다.
이 노트는 보도·비평·교육·연구 목적으로 작성되었습니다. 저작권 문의가 있으시면 에서 알려주세요.