재귀 — 콜 스택과 자기 참조적 사고방식

🎯 이 강의에서 배우는 것

재귀(recursion)는 함수가 자기 자신을 호출하는 기법입니다. 단순히 문법적 패턴이 아니라 자기 참조적 사고방식(self-referential thinking)입니다. 재귀로 생각하면 트리 순회, 분할 정복, 백트래킹 같은 복잡한 문제가 놀랍도록 단순해집니다. 이 강의에서 콜 스택 수준의 원리부터 실전 재귀 설계까지 배웁니다.

📚 콜 스택과 재귀 — 팩토리얼로 이해하기

def factorial(n):
    if n == 0:        # 기저 조건 (Base Case)
        return 1
    return n * factorial(n - 1)   # 귀납 단계 (Inductive Step)

# factorial(4) 호출 시 콜 스택:
# ┌─────────────────────┐  ← 최상단 (가장 나중에 쌓임)
# │ factorial(0): n=0   │  → return 1
# ├─────────────────────┤
# │ factorial(1): n=1   │  → return 1 * 1 = 1
# ├─────────────────────┤
# │ factorial(2): n=2   │  → return 2 * 1 = 2
# ├─────────────────────┤
# │ factorial(3): n=3   │  → return 3 * 2 = 6
# ├─────────────────────┤
# │ factorial(4): n=4   │  → return 4 * 6 = 24
# └─────────────────────┘  ← 최하단 (처음 호출)

print(factorial(4))   # 24

# 각 스택 프레임은 독립적인 n을 가짐 — LEGB의 Local 스코프
# 재귀가 깊어질수록 스택이 쌓임 → 메모리 사용량 O(n)

# 스택 추적 시각화
import sys

def factorial_traced(n, depth=0):
    indent = "  " * depth
    print(f"{indent}→ factorial({n})")
    if n == 0:
        print(f"{indent}← return 1")
        return 1
    result = n * factorial_traced(n - 1, depth + 1)
    print(f"{indent}← return {result}")
    return result

factorial_traced(4)

🛡️ 기저 조건 설계 — RecursionError 방지

import sys
print(sys.getrecursionlimit())   # 기본값: 1000

# 기저 조건 없으면 무한 재귀 → RecursionError
def bad_factorial(n):
    return n * bad_factorial(n - 1)   # 기저 조건 없음!
# bad_factorial(5)  ← RecursionError: maximum recursion depth exceeded

# 기저 조건 설계 원칙:
# 1. 재귀가 반드시 기저 조건을 향해 수렴해야 함
# 2. 기저 조건에서는 재귀 호출 없이 직접 반환
# 3. 각 재귀 호출은 문제를 "작게" 만들어야 함

def count_down(n):
    if n <= 0:        # 기저 조건: 수렴 보장
        print("발사!")
        return
    print(n)
    count_down(n - 1)  # n이 줄어드니까 반드시 기저 조건 도달

count_down(5)
# 5, 4, 3, 2, 1, 발사!

# 재귀 깊이 늘리기 (필요할 때만 — 조심해서 사용)
# sys.setrecursionlimit(5000)

🐌 피보나치의 비극 — 재귀의 시간 복잡도

import time

# 순진한 재귀 피보나치: O(2^n) 시간
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n-1) + fib_naive(n-2)

# fib(40): 약 1억 3000만 번 호출!
# fib(50): 천억 번 이상 — 사실상 불가능

# 중복 계산 시각화 (fib(5))
call_count = 0
def fib_count(n):
    global call_count
    call_count += 1
    if n <= 1:
        return n
    return fib_count(n-1) + fib_count(n-2)

call_count = 0
fib_count(10)
print(f"fib(10) 호출 횟수: {call_count}")   # 177번!

# 메모이제이션으로 O(n) 개선
from functools import lru_cache

@lru_cache(maxsize=None)   # 무제한 캐시
def fib_cached(n):
    if n <= 1:
        return n
    return fib_cached(n-1) + fib_cached(n-2)

start = time.perf_counter()
print(fib_cached(100))   # 354224848179261915075
print(f"시간: {time.perf_counter()-start:.6f}초")   # 거의 0초!

# 반복문으로 O(n) 시간, O(1) 공간
def fib_iterative(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

print(fib_iterative(100))   # 354224848179261915075

🏗️ 재귀 설계 3단계

# 3단계: ① 함수 명세 → ② 기저 조건 → ③ 재귀 단계

# 예제 1: 리스트 합계
# ① sum_list(lst)는 lst의 모든 원소 합을 반환
# ② 기저: lst가 비어있으면 0
# ③ 재귀: 첫 원소 + sum_list(나머지)
def sum_list(lst):
    if not lst:            # ② 기저 조건
        return 0
    return lst[0] + sum_list(lst[1:])   # ③ 재귀

print(sum_list([1, 2, 3, 4, 5]))   # 15

# 예제 2: 하노이 탑
# ① hanoi(n, from_peg, to_peg, aux_peg) — n개 원판을 from에서 to로 이동
# ② 기저: n == 1 → 직접 이동
# ③ 재귀: n-1개를 aux로, 1개를 to로, n-1개를 to로
def hanoi(n, from_peg, to_peg, aux_peg):
    if n == 1:   # ② 기저 조건
        print(f"원판 1: {from_peg} → {to_peg}")
        return
    hanoi(n-1, from_peg, aux_peg, to_peg)   # n-1개를 보조로
    print(f"원판 {n}: {from_peg} → {to_peg}")   # 가장 큰 원판 이동
    hanoi(n-1, aux_peg, to_peg, from_peg)    # n-1개를 목표로

hanoi(3, "A", "C", "B")   # 7번 이동으로 해결

# 예제 3: 디렉토리 탐색 (트리 구조 재귀)
import os

def list_files(path, indent=0):
    prefix = "  " * indent
    try:
        if os.path.isfile(path):
            print(f"{prefix}{os.path.basename(path)}")
        elif os.path.isdir(path):
            print(f"{prefix}{os.path.basename(path)}/")
            for entry in sorted(os.listdir(path)):
                list_files(os.path.join(path, entry), indent + 1)
    except PermissionError:
        print(f"{prefix}[접근 거부]")

# list_files("C:/Users/chung/Documents")

🔄 꼬리 재귀와 반복문 변환

# 꼬리 재귀(tail recursion): 재귀 호출이 마지막 연산
def factorial_tail(n, accumulator=1):
    if n == 0:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)   # 꼬리 재귀

# 파이썬은 꼬리 재귀 최적화(TCO, Tail Call Optimization)를 지원 안 함!
# Guido van Rossum이 의도적으로 제외 (스택 트레이스 유지 목적)
# 따라서 스택은 여전히 O(n)으로 쌓임

# 깊은 재귀가 필요하면 명시적 반복문으로 변환:
def factorial_iter(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

# 또는 스택을 직접 시뮬레이션
def hanoi_iter(n, from_peg, to_peg, aux_peg):
    # 명시적 스택으로 재귀를 반복문으로 변환
    stack = [(n, from_peg, to_peg, aux_peg)]
    moves = []
    while stack:
        n, fr, to, aux = stack.pop()
        if n == 1:
            moves.append(f"원판 1: {fr} → {to}")
        else:
            stack.append((n-1, aux, to, fr))   # 마지막 단계를 먼저 push
            stack.append((1, fr, to, aux))
            stack.append((n-1, fr, aux, to))   # 첫 단계를 나중에 push
    return moves

⚠️ 자주 하는 실수

• 기저 조건 누락: 재귀 함수는 반드시 기저 조건이 있어야 합니다. "이 경우에는 무엇을 반환해야 하는가"를 먼저 정의하세요. 기저 조건이 없으면 RecursionError가 발생합니다.
• 재귀가 기저 조건으로 수렴하지 않음: factorial(-1) 처럼 n이 음수면 기저 조건(n==0)에 영원히 도달 못합니다. 입력 유효성 검사나 기저 조건 범위 확장이 필요합니다.
• 순진한 재귀 피보나치를 큰 n에 사용: fib(40) 이상은 실용적이지 않습니다. @lru_cache를 사용하거나 반복문으로 전환하세요.

📝 정리 및 다음 강의 예고

• 재귀 = 기저 조건(Base Case) + 귀납 단계(Inductive Step). 재귀 호출은 반드시 기저 조건을 향해 수렴해야 합니다.
• 콜 스택: 각 재귀 호출은 독립적인 스택 프레임을 가집니다. 파이썬 기본 한도는 1000입니다.
• 중복 재귀(피보나치)는 @lru_cache나 반복문으로 최적화하세요.
• 파이썬은 꼬리 재귀 최적화를 지원하지 않으므로, 깊은 재귀는 반복문으로 변환하세요.

다음 강의: 데코레이터 — 함수를 감싸는 함수. 클로저로 데코레이터를 직접 구현하고, functools.wraps, 인자 있는 데코레이터, 클래스 데코레이터까지 배웁니다.