재귀 함수 — 자기 자신을 호출하는 함수

이 토픽을 마치면

재귀 함수의 작동 원리를 설명할 수 있고, 종료 조건(base case)의 중요성을 이해하며, 간단한 재귀 문제를 직접 풀 수 있습니다.

재귀란 무엇인가

재귀(recursion)는 함수가 자기 자신을 호출하는 것입니다.

python

def countdown(n):
    if n <= 0:
        print("Launch!")
        return
    print(n)
    countdown(n - 1)  # 자기 자신을 호출

countdown(5)
# 5
# 4
# 3
# 2
# 1
# Launch!

countdown(5)가 countdown(4)를 호출하고, countdown(4)가 countdown(3)을 호출하고... countdown(0)이 되면 "Launch!"를 출력하고 멈춥니다.

이것이 재귀의 전부입니다. 두 가지 요소가 있습니다:

종료 조건 (Base Case): if n <= 0 — 더 이상 호출하지 않는 조건
재귀 단계 (Recursive Case): countdown(n - 1) — 자신을 호출하되, 문제를 더 작게 만듦

왜 종료 조건이 필수인가

종료 조건이 없으면 무한히 자기 자신을 호출합니다.

python

def infinite():
    print("Help!")
    infinite()  # 영원히 호출

infinite()
# Help!
# Help!
# Help!
# ...
# RecursionError: maximum recursion depth exceeded

Python은 기본적으로 1,000번까지만 재귀를 허용합니다. 그 이상이면 RecursionError로 강제 종료합니다. 이것은 무한 재귀로 메모리가 폭발하는 것을 방지하는 안전장치입니다.

팩토리얼 — 재귀의 교과서 예제

5! = 5 × 4 × 3 × 2 × 1 = 120

팩토리얼을 재귀적으로 생각하면: 5! = 5 × 4!

python

def factorial(n):
    # Base case
    if n <= 1:
        return 1
    # Recursive case
    return n * factorial(n - 1)

print(factorial(5))  # 120

호출 과정을 따라가면:

text

factorial(5)
  → 5 * factorial(4)
       → 4 * factorial(3)
            → 3 * factorial(2)
                 → 2 * factorial(1)
                      → 1  (base case!)
                 ← 2 * 1 = 2
            ← 3 * 2 = 6
       ← 4 * 6 = 24
  ← 5 * 24 = 120

함수가 "깊이 들어갔다가" 결과를 가지고 "다시 올라오는" 구조입니다.

콜 스택 — 재귀가 작동하는 원리

함수가 호출될 때마다, 컴퓨터는 스택(stack) 이라는 메모리 공간에 현재 상태를 저장합니다.

text

factorial(5) 호출 → 스택: [factorial(5)]
factorial(4) 호출 → 스택: [factorial(5), factorial(4)]
factorial(3) 호출 → 스택: [factorial(5), factorial(4), factorial(3)]
factorial(2) 호출 → 스택: [factorial(5), factorial(4), factorial(3), factorial(2)]
factorial(1) 호출 → 스택: [factorial(5), factorial(4), factorial(3), factorial(2), factorial(1)]
factorial(1) 반환 → 스택: [factorial(5), factorial(4), factorial(3), factorial(2)]
factorial(2) 반환 → 스택: [factorial(5), factorial(4), factorial(3)]
...

재귀가 깊어질수록 스택이 쌓입니다. Python의 기본 한도가 1,000인 이유 — 스택 하나당 메모리를 차지하므로, 너무 깊으면 메모리가 부족해집니다.

피보나치 — 재귀의 함정

python

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(10))  # 55
print(fib(30))  # 832040 — but slow!
# print(fib(50))  # Never finishes...

코드는 간결하지만, fib(50)은 영원히 끝나지 않습니다. 같은 값을 반복 계산하기 때문입니다.

text

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2) ← repeated
│   │   └── fib(1)
│   └── fib(2) ← repeated
└── fib(3) ← repeated
    ├── fib(2) ← repeated
    └── fib(1)

fib(2)가 여러 번 계산됩니다. fib(30)에서는 수백만 번, fib(50)에서는 수십억 번 중복 계산이 발생합니다.

메모이제이션으로 해결

python

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_fast(n):
    if n <= 1:
        return n
    return fib_fast(n - 1) + fib_fast(n - 2)

print(fib_fast(50))   # 12586269025 — instant!
print(fib_fast(100))  # 354224848179261915075

@lru_cache는 이미 계산한 결과를 저장해두고, 같은 인자로 호출되면 저장된 값을 반환합니다. 중복 계산이 사라지므로 O(2^n)이 O(n)으로 줄어듭니다.

재귀 vs 반복문

같은 문제를 반복문으로도 풀 수 있습니다.

python

# Recursion
def factorial_rec(n):
    if n <= 1:
        return 1
    return n * factorial_rec(n - 1)

# Iteration
def factorial_iter(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

비교	재귀	반복문
가독성	문제 구조가 재귀적이면 직관적	단순 반복은 더 명확
성능	콜 스택 오버헤드 있음	일반적으로 더 빠름
메모리	스택 깊이만큼 사용	O(1)
적합한 문제	트리 탐색, 분할 정복, 순열/조합	단순 반복, 누적 계산

규칙: 문제의 구조가 자연스럽게 재귀적이면(트리, 그래프, 분할 정복) 재귀를 쓰고, 단순 반복이면 for 루프를 씁니다.

실전 예제 — 디렉토리 탐색

python

import os

def list_all_files(directory, indent=0):
    """Recursively list all files in a directory tree."""
    items = sorted(os.listdir(directory))
    for item in items:
        path = os.path.join(directory, item)
        print("  " * indent + item)
        if os.path.isdir(path):
            list_all_files(path, indent + 1)  # subdirectory → recurse

list_all_files("project")
# project
#   app.js
#   routes
#     users.js
#     posts.js
#   public
#     css
#       style.css
#     index.html

폴더 안에 폴더가 있고, 그 안에 또 폴더가 있는 구조 — 이것이 전형적인 재귀 문제입니다. "몇 단계까지 있는지 모르지만, 같은 패턴이 반복된다"면 재귀가 자연스럽습니다.

핵심 정리

개념	정리
재귀	함수가 자기 자신을 호출
Base Case	더 이상 재귀하지 않는 종료 조건 (필수)
Recursive Case	문제를 더 작게 만들어 자신을 호출
콜 스택	호출마다 메모리에 상태 저장 (Python 한도 1,000)
메모이제이션	중복 계산 방지 (`@lru_cache`)

재귀를 처음 보면 "함수가 자기 자신을 호출하면 무한 루프 아닌가?"라는 의문이 듭니다. 핵심은 매번 문제가 더 작아져서, 결국 종료 조건에 도달한다는 것입니다. 이 패턴을 이해하면, 트리 탐색, 정렬(병합 정렬), 조합/순열, 그래프 탐색(DFS) 등 많은 알고리즘을 자연스럽게 이해할 수 있습니다.

실전 패턴 — 중첩 딕셔너리 탐색

JSON이나 설정 파일에서 깊이를 모르는 중첩 구조를 만나면, 재귀가 자연스럽습니다.

python

def flatten_dict(d, prefix=""):
    result = {}
    for key, value in d.items():
        full_key = f"{prefix}.{key}" if prefix else key
        if isinstance(value, dict):
            result.update(flatten_dict(value, full_key))
        else:
            result[full_key] = value
    return result

config = {
    "database": {
        "host": "localhost",
        "port": 5432,
        "credentials": {
            "user": "admin",
            "password": "secret"
        }
    },
    "debug": True
}

print(flatten_dict(config))
# {
#   'database.host': 'localhost',
#   'database.port': 5432,
#   'database.credentials.user': 'admin',
#   'database.credentials.password': 'secret',
#   'debug': True
# }

이 패턴은 로그 시스템, 설정 관리, Elasticsearch 인덱싱 등에서 자주 사용됩니다.