재귀 알고리즘 설계: 기저 사례부터 메모이제이션까지

재귀는 문제를 더 작은 하위 문제로 쪼갠 뒤 같은 절차를 다시 적용하는 알고리즘 구성 방식이다. 함수가 자신을 직접 또는 간접 호출하며, 트리·그래프 탐색, 파싱, 백트래킹, 동적 계획법에서 문제 구조를 코드에 그대로 옮기기 좋다.

재귀 호출은 아래로 내려가며 상태를 쌓고, 반환 과정에서 부분 결과를 합쳐 답을 만든다. 이 구조가 성립하려면 더 이상 나눌 수 없는 입력을 처리하는 기저 사례(Base Case)와, 입력을 줄이는 재귀 단계(Recursive Step)가 모두 필요하다.

종료를 보장하는 기저 사례와 축소 규칙

기저 사례가 없으면 호출은 끝나지 않는다. 재귀 단계에서는 입력 크기가 단조롭게 줄어들거나 문제 크기가 축소된다는 불변식을 세워 유한성을 보장해야 한다.

정확성은 수학적 귀납법으로 점검할 수 있다. 기저 사례가 올바른지 확인하고, 더 작은 문제에서 성립한다는 가정 아래 재귀 단계가 올바른 결과를 만드는지 검증한다. 불변식과 변량(Variant)을 함께 두면 수렴성과 부분정확성도 다룰 수 있다.

호출 스택이 재귀의 운영 한계를 만든다

함수가 호출될 때마다 새로운 스택 프레임이 만들어지고, 프레임에는 매개변수·지역 변수·복귀 주소가 보관된다. 이 때문에 깊이가 커지는 재귀는 스택 오버플로 위험을 가진다.

입력 유효성을 확인하고 최대 깊이를 고려해야 하며, 큰 입력에서는 반복문으로 전환하거나 분할 처리하는 선택지가 필요하다. 꼬리 재귀는 마지막 연산이 자기 호출인 형태이며, TCO를 지원하는 언어에서는 스택 사용을 줄일 수 있다. 다만 런타임마다 지원 여부가 다르다.

분할 정복과 중복 부분문제 처리

분할 정복은 문제를 균등하거나 불균등하게 나누고, 하위 문제의 결과를 결합해 전체 해를 구한다. 비용은 다음과 같은 재귀식으로 모델링할 수 있다.

T(n) = aT(n/b) + f(n)

여기서 하위 문제의 수와 크기뿐 아니라 결합 비용 f(n)도 분석 대상이다.

반복되는 하위 문제가 있다면 메모이제이션으로 결과를 캐싱할 수 있다. 시간 복잡도를 낮출 수 있지만, 캐시가 차지하는 메모리와 캐시 무효화 전략이라는 공간-시간 트레이드오프가 생긴다.

설계할 때 확인할 흐름

문제를 자연스럽게 부분 문제로 분해할 수 있는지 먼저 본다. 그 다음 최소 입력의 해를 기저 사례로 정하고, 입력 축소 규칙과 결합 연산을 재귀 단계에 넣는다. 재귀식을 세워 복잡도를 모델링한 뒤 최대 깊이, 입력 검증, 예외 처리, 메모이제이션·꼬리 재귀·반복 변환 여부를 결정한다.

⤢✕

계층 구조와 탐색 공간을 다룰 때

트리·그래프에서는 DFS, 서브트리 합산, LCA, 경로 탐색에 재귀를 적용할 수 있다. 파일 시스템 크롤링, 카테고리·권한 트리 평가, JSON/XML 계층 변환도 같은 구조를 가진다.

재귀 하향 파서(Recursive Descent Parsing)는 문법 규칙을 함수로 나누어 표현한다. AST 생성 이후 재귀적 의미 분석과 코드 생성 단계까지 연결할 수 있다.

백트래킹에서는 N-Queen, 순열·조합 생성, 제약 충족 문제를 탐색한다. 가지치기(Pruning)와 휴리스틱을 적용해 탐색 공간을 줄인다.

동적 계획법의 Top-Down 방식은 피보나치, 편집 거리, 배낭 문제 등에 메모이제이션을 적용한다. 중복 호출을 없애 O(exponential)을 O(polynomial)로 바꾼다.

Merge Sort, Quick Sort, Karatsuba 곱셈, 병렬 합산도 분할 정복 구조를 사용한다. 작업을 나누고 풀·스레드를 활용해 멀티코어 자원을 활용할 수 있다.

반복문과 비교해 선택하기

구분	성능	확장성	일관성	안정성	운영 편의
재귀	호출 오버헤드 존재, 분할 정복에서 우수	깊이에 따른 스택 한계, TCO 지원 시 개선	수학적 정의와 코드 구조 일치	스택 오버플로 리스크, 기저 사례 결여 시 위험	트리/문법 처리 가독성 우수
반복	오버헤드 낮음, 상수 비용 유리	스택 한계 없음, 대규모 입력 안정	상태 머신/루프 불변식으로 명시적	제어 흐름 명확, 예외 처리 단순	스택 에뮬레이션 시 코드 장황

Python에서 보는 재귀 구현

전제조건: Python 3.11+, 메모리/스택 기본 설정 사용. CPython은 TCO 미지원.

팩토리얼의 기저 사례와 입력 검증

def factorial(n: int) -> int:
    if not isinstance(n, int):
        raise TypeError("정수 필요")
    if n < 0:
        raise ValueError("음수 불가")
    if n in (0, 1):  # 기저 사례
        return 1
    return n * factorial(n - 1)  # 재귀 단계

print(factorial(5))  # 120

캐시를 적용한 피보나치 O(n)

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n: int) -> int:
    if n < 0:
        raise ValueError("음수 불가")
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(40))  # 캐시 활용

DFS를 반복문으로 바꾸는 방법

# 재귀 DFS
def dfs_recursive(graph, v, visited=None):
    if visited is None:
        visited = set()
    visited.add(v)
    for nxt in graph.get(v, []):
        if nxt not in visited:
            dfs_recursive(graph, nxt, visited)
    return visited

# 반복 DFS(스택 에뮬레이션)
def dfs_iterative(graph, start):
    visited, stack = set(), [start]
    while stack:
        v = stack.pop()
        if v in visited:
            continue
        visited.add(v)
        stack.extend(reversed(graph.get(v, [])))  # 순서 제어
    return visited

꼬리 재귀 형태와 CPython의 제약

def sum_tail(nums, acc=0, idx=0):
    if idx == len(nums):  # 꼬리 위치의 종료
        return acc
    return sum_tail(nums, acc + nums[idx], idx + 1)

# 큰 입력은 반복으로 대체 권장
def sum_iter(nums):
    acc = 0
    for x in nums:
        acc += x
    return acc

CPython은 Tail Call Optimization을 지원하지 않는다. 큰 입력은 반복 변환 또는 분할 처리로 대체하는 편이 낫다.

코드 구조를 단순하게 만드는 범위와 비용

재귀 구조는 코드 길이를 20~40% 축소할 수 있고, 로직의 가독성을 높인다. 분할 정복을 적용하면 Merge/Quick에서 O(n log n) 정렬을 달성할 수 있으며, 메모이제이션은 지수 시간을 선형/다항 시간으로 바꾼다.

문제 정의와 코드 구조가 등형성을 가지면 변경 영향 범위를 줄이고 단위 테스트를 쉽게 구성할 수 있다. 반면 운영 환경에서는 깊이 제한, 입력 검증, 폴백 반복 구현으로 스택 오버플로 리스크를 관리해야 한다.

기저 사례를 명확히 두고 입력 검증과 최대 깊이 제한을 설정한다. 메모이제이션을 사용할 때는 캐시 무효화 전략과 메모리 상한을 모니터링한다. 병렬 재귀에서는 작업 단위 임계값(Thresholding), 스레드·풀 크기도 제어 대상이다.

재귀의 간결성과 반복문의 상수 비용 이점, 캐시를 통한 시간 절약과 메모리 증가, TCO 의존 코드의 런타임별 동작 차이를 함께 고려해야 한다.