재귀 함수 원리와 파이썬 예제로 이해하기

재귀가 해결하는 문제

어떤 문제는 자기 자신으로 정의됩니다. 폴더에는 파일과 다른 폴더가 들어 있고, 트리 노드에는 자식 트리가 달려 있으며, n의 팩토리얼은 n에 n − 1의 팩토리얼을 곱한 값입니다. 이런 문제를 단순한 반복문으로 풀려면 처리할 일을 담아 둘 스택을 직접 관리해야 하는 경우가 많습니다. 재귀를 쓰면 그 스택을 언어가 대신 관리해 줍니다.

재귀 함수는 두 부분으로 이루어집니다.

• 기저 조건(base case): 바로 답할 수 있는 가장 작은 입력입니다. 팩토리얼에서는 0! = 1입니다.
• 재귀 단계(recursive case): 문제를 줄여 더 작은 부분에 함수를 호출하고 결과를 합칩니다. 팩토리얼에서는 n! = n × (n − 1)!입니다.

def factorial(n):
    if n == 0:                  # base case
        return 1
    return n * factorial(n - 1) # recursive case
print(factorial(5))   # 120

호출 스택을 단계별로 추적하기

각 호출은 호출 스택에 자기만의 프레임을 가지며, 그 안에 n의 복사본이 들어 있습니다. 호출은 기저 조건까지 내려가고, 그 뒤 결과가 역순으로 올라옵니다.

여기서 스택 깊이는 n + 1개 프레임이므로, 리스트를 만들지 않아도 추가 공간은 O(n)입니다.

중첩된 데이터에서의 재귀

데이터 구조 자체가 재귀적일 때 재귀가 가장 유용합니다. 다음 함수는 다른 리스트가 몇 단계로 중첩되어 있어도 그 안의 모든 숫자를 더합니다.

def deep_sum(items):
    total = 0
    for x in items:
        if isinstance(x, list):
            total += deep_sum(x)   # same problem, smaller piece
        else:
            total += x
    return total
print(deep_sum([1, [2, 3], [4, [5, [6]]]]))   # 21

같은 패턴으로 디렉터리 트리, JSON 문서, HTML DOM, 이진 트리도 순회할 수 있습니다. 현재 노드를 처리한 다음 각 자식에 대해 재귀 호출을 합니다.

def power_set(items):
    if not items:
        return [[]]
    rest = power_set(items[1:])
    return rest + [[items[0]] + s for s in rest]
print(power_set([1, 2, 3]))
# [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

재귀 함수의 복잡도

비용은 (호출 횟수) × (호출당 작업량)으로 추정합니다. 공간은 최소한 스택의 최대 깊이만큼 듭니다.

병합 정렬의 T(n) = 2T(n/2) + O(n) 같은 분할 정복 점화식은 O(n log n)으로 풀립니다. n − 1에 대해 두 번 호출하는 함수는 지수적으로 증가합니다.

메모이제이션: 반복 계산 막기

단순한 피보나치 함수는 같은 값을 여러 번 다시 계산합니다. fib(5)는 fib(3)을 두 번, fib(2)를 세 번 호출합니다. 각 결과를 처음 계산할 때 캐시에 저장하면 지수 시간이 선형 시간으로 줄어듭니다. 파이썬의 functools.lru_cache(또는 파이썬 3.9 이상의 functools.cache)는 데코레이터 하나로 이를 처리합니다.

from functools import lru_cache
def fib_slow(n):
    return n if n < 2 else fib_slow(n - 1) + fib_slow(n - 2)
@lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)
print(fib_slow(20))   # 6765, about 22,000 calls
print(fib(90))        # 2880067194370816120, 91 distinct calls

메모이제이션을 적용한 재귀는 동적 계획법의 하향식(top-down) 형태입니다. 상향식(bottom-up) 형태는 반복문으로 표를 채웁니다.

재귀 깊이 제한과 반복문으로 바꾸기

sys.setrecursionlimit()으로 제한을 올릴 수는 있지만, 아주 깊은 재귀는 여전히 인터프리터를 비정상 종료시킬 수 있습니다. 노드가 100만 개인 연결 리스트나 한쪽으로 치우친 트리처럼 깊어질 수 있는 입력에는 함수를 반복문과 명시적 스택으로 다시 작성하세요.

def deep_sum_iter(items):
    total, stack = 0, [items]
    while stack:
        current = stack.pop()
        for x in current:
            if isinstance(x, list):
                stack.append(x)
            else:
                total += x
    return total
print(deep_sum_iter([1, [2, 3], [4, [5, [6]]]]))   # 21

흔한 실수

• 기저 조건이 없거나 도달할 수 없는 경우입니다. 예를 들어 위 코드에서 factorial(-1)은 0에 도달하지 못하고 RecursionError로 끝납니다.
• 입력이 줄어들지 않는 재귀 단계입니다. 예를 들어 f(n) 안에서 f(n)을 호출하는 경우입니다.
• 재귀 결과를 return하는 것을 잊는 경우입니다. return 없이 factorial(n - 1)만 쓰면 None이 됩니다.
• 호출할 때마다 데이터를 복사하는 경우입니다. items[1:]은 리스트를 복사하므로, 긴 리스트의 슬라이스로 재귀하면 시간이 O(n²) 듭니다. 대신 인덱스를 넘기세요.
• 호출 사이에 상태를 전달하려고 def f(x, seen=[])처럼 변경 가능한 기본 인자를 쓰는 경우입니다. 같은 리스트가 함수의 모든 호출에서 공유됩니다.

재귀를 쓰기 좋은 때

데이터나 문제가 본질적으로 재귀적일 때 재귀를 쓰세요. 트리, 그래프(깊이 우선 탐색), 중첩 구조, 수식 파싱, 백트래킹(순열, N-Queens, 스도쿠), 분할 정복(병합 정렬, 퀵 정렬, 이진 탐색)이 그런 경우입니다. 문제가 단순한 순차 처리이거나 파이썬에서 입력 크기에 따라 깊이가 커질 수 있다면 반복문을 쓰세요.

면접에서 재귀 문제는 기저 조건과 재귀 단계, 스택을 포함한 시간·공간 비용, 메모이제이션이 도움이 되는 때를 설명할 수 있는지 묻는 경우가 많습니다.