13강. 재귀 | 코딩 테스트 합격 알고리즘 30강 · 중급 — 누구나패스

🎯 학습 목표

이 강을 마치면 재귀 함수를 기저 조건과 재귀 단계로 나눠 설계할 수 있습니다. 그리고 재귀가 내부적으로 호출 스택으로 동작한다는 것을 이해하고, 파이썬의 재귀 깊이 제한과 메모이제이션을 다룰 수 있게 됩니다.

재귀는 뒤에 나올 분할 정복(14강)·백트래킹(16강)·트리(19강)·DFS(23강)·DP(26강)의 공통 토대입니다. 여기서 확실히 잡아야 뒤가 편합니다.

💡 기저 조건과 재귀 단계

재귀는 함수가 자기 자신을 부르는 것입니다. 문제를 같은 모양의 더 작은 문제로 바꿔 푸는 방식입니다.

모든 재귀 함수는 반드시 두 부분으로 이루어집니다.

기저 조건(base case) — 더 이상 쪼개지 않고 즉시 답을 돌려주는 지점
재귀 단계(recursive case) — 더 작은 문제를 호출해 답을 만드는 지점

팩토리얼 5! 의 호출 과정

  factorial(5)
   → 5 × factorial(4)
        → 4 × factorial(3)
             → 3 × factorial(2)
                  → 2 × factorial(1)
                       → 1  ← 기저 조건. 여기서 멈춘다
                  ← 2 × 1 = 2
             ← 3 × 2 = 6
        ← 4 × 6 = 24
   ← 5 × 24 = 120

  ▲ 두 방향이 있다
   내려가는 길 : 문제를 쪼갠다
   올라오는 길 : 결과를 합친다

  ▲ 기저 조건이 없으면
    factorial(1) → 1 × factorial(0) → 0 × factorial(-1) → ...
    영원히 내려가다 오류가 난다

  호출 스택 — 재귀는 스택으로 동작한다 (5강)

   호출할 때마다 지역 변수와 돌아갈 위치가 스택에 쌓인다

        ┌───────────────┐
        │ factorial(1)  │ ← 지금 실행 중
        ├───────────────┤
        │ factorial(2)  │
        ├───────────────┤
        │ factorial(3)  │
        ├───────────────┤
        │ factorial(4)  │
        ├───────────────┤
        │ factorial(5)  │
        └───────────────┘

   기저 조건에 닿으면 위에서부터 하나씩 걷히며 값을 돌려준다

  ▲ 그래서 재귀의 공간 복잡도는 '깊이'다
    깊이가 n이면 공간 O(n)

재귀 함수를 설계할 때는 세 가지 질문을 순서대로 던지면 됩니다.

언제 멈추는가? — 기저 조건
어떻게 더 작게 만드는가? — 인자를 어떻게 줄일 것인가
작은 답으로 큰 답을 어떻게 만드는가? — 결합 방법

📖 재귀의 비용과 메모이제이션

재귀는 코드가 간결해지지만 비용이 숨어 있습니다. 대표적인 예가 피보나치입니다.

fib(5) 를 단순 재귀로 계산하면

              fib(5)
            /        \
           fib(4)      fib(3)
        /     \       /    \
     fib(3)  fib(2) fib(2) fib(1)
     /   \
  fib(2) fib(1)

  ▲ fib(3) 이 2번, fib(2) 가 3번 계산된다
    n이 커지면 중복이 폭발한다 → 대략 O(2ⁿ)

    fib(40) 은 수억 번의 호출이 필요하다

  ▲ 메모이제이션 — 한 번 계산한 값을 기억한다

    fib(3) 을 처음 계산했을 때 저장해 두고
    다음에 필요하면 꺼내 쓴다

    → 각 n에 대해 딱 한 번만 계산 → O(n)

  ▲ 이것이 26강 동적 계획법의 출발점이다

파이썬은 메모이제이션을 데코레이터 한 줄로 제공합니다. functools.lru_cache 또는 functools.cache를 함수 위에 붙이면 됩니다.

또 하나 중요한 제약이 있습니다. 파이썬의 재귀 깊이 제한입니다. 기본값은 1,000이고, sys.getrecursionlimit()으로 확인할 수 있습니다. 깊이가 이를 넘으면 RecursionError가 납니다.

깊이 제한 대응

  ① 한도를 올린다
     import sys
     sys.setrecursionlimit(10 ** 6)
     ⚠️ 무한정 안전하지 않다. 실제 스택 메모리가 부족하면
       프로세스가 비정상 종료될 수 있다.

  ② 반복문으로 바꾼다  ← 가장 안전
     선형 재귀(자기 자신을 한 번만 호출)는
     대부분 while 반복문으로 바꿀 수 있다

  ③ 명시적 스택을 쓴다
     DFS 를 재귀 대신 스택으로 구현하는 방식 (23강)

  ▲ 파이썬은 꼬리 재귀 최적화를 하지 않는다.
    다른 언어에서 안전한 형태여도 파이썬에서는
    깊이만큼 스택이 쌓인다.

  ▲ 코딩 테스트 실무 감각
    n이 10만 규모인데 재귀 깊이가 n에 비례한다면
    반복문이나 명시적 스택으로 바꾸는 편이 안전하다.

💻 실전 예제 — 재귀 세 가지

import sys
from functools import lru_cache


def factorial(n):
    """n! → 깊이 n 의 선형 재귀"""
    if n <= 1:                    # 기저 조건
        return 1
    return n * factorial(n - 1)   # 재귀 단계


def fib_slow(n):
    """단순 재귀 피보나치 → O(2^n). n이 크면 매우 느리다"""
    if n < 2:
        return n
    return fib_slow(n - 1) + fib_slow(n - 2)


@lru_cache(maxsize=None)
def fib_fast(n):
    """메모이제이션 피보나치 → O(n)"""
    if n < 2:
        return n
    return fib_fast(n - 1) + fib_fast(n - 2)


def fib_loop(n):
    """반복문 버전 → O(n), 공간 O(1), 깊이 제한 없음"""
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a


def hanoi(n, start, end, via, moves):
    """하노이 탑 : n개를 start 에서 end 로 옮기는 순서"""
    if n == 0:
        return
    hanoi(n - 1, start, via, end, moves)   # 위 n-1개를 경유지로
    moves.append((start, end))             # 가장 큰 것을 목적지로
    hanoi(n - 1, via, end, start, moves)   # 경유지의 n-1개를 목적지로


print(factorial(5))                 # 120
print(fib_fast(50))                 # 12586269025
print(fib_loop(50))                 # 12586269025
print(sys.getrecursionlimit())      # 1000 (기본값)

log = []
hanoi(3, "A", "C", "B", log)
print(len(log), log[:3])            # 7 [('A','C'), ('A','B'), ('C','B')]

코드를 줄 단위로 보겠습니다.

if n <= 1: return 1 — 가장 먼저 쓰는 줄입니다. 기저 조건을 맨 위에 두는 습관을 들이면 무한 재귀를 막을 수 있습니다.
@lru_cache(maxsize=None) — 데코레이터입니다. 같은 인자로 다시 호출되면 계산하지 않고 저장된 값을 돌려줍니다. 이 한 줄로 O(2ⁿ)이 O(n)이 됩니다.
lru_cache는 인자를 딕셔너리 키로 쓰므로, 인자가 해시 가능해야 합니다(7강). 리스트를 인자로 받는 함수에는 쓸 수 없습니다.
a, b = b, a + b — 반복문 버전의 핵심입니다. 오른쪽이 먼저 전부 계산된 뒤 왼쪽에 할당되므로 임시 변수가 필요 없습니다.
fib_loop는 공간 O(1)이고 깊이 제한이 없습니다. 선형 재귀는 대개 반복문으로 바꿀 수 있다는 예시입니다.
hanoi(n - 1, start, via, end, moves) — 하노이 탑은 반복문으로 바꾸기 어려운 재귀입니다. 자기 자신을 두 번 호출하며 문제 구조 자체가 재귀적이기 때문입니다.
하노이의 이동 횟수는 2ⁿ - 1입니다. n=3이면 7번입니다. 재귀 호출 횟수가 곧 복잡도가 되는 전형적인 예입니다.

fib_slow(50)은 실행하지 마세요. 수십 년이 걸릴 수 있습니다. fib_slow(30) 정도로 체감해 보고 fib_fast와 비교하면 메모이제이션의 위력을 알 수 있습니다.

⚠️ 자주 하는 실수

첫째, 기저 조건을 빠뜨리거나 잘못 잡습니다. 가장 흔한 재귀 버그입니다. 기저 조건이 반드시 도달 가능한지 확인하세요. n == 1만 기저로 두고 n이 0이나 음수로 들어올 수 있다면 무한 재귀가 됩니다. n <= 1처럼 범위로 잡는 편이 안전합니다.

둘째, 인자가 줄어들지 않습니다. f(n) 안에서 f(n)을 부르면 영원히 반복됩니다. 매 호출마다 문제가 확실히 작아지는지 확인하세요.

셋째, 재귀 깊이를 계산하지 않습니다. n이 10만인데 깊이가 n이면 RecursionError가 납니다. 한도를 올리는 것보다 반복문이나 명시적 스택이 안전합니다.

넷째, 중복 계산을 방치합니다. 같은 인자로 여러 번 호출되는 구조라면 lru_cache 한 줄로 극적으로 빨라집니다. 재귀를 짜고 나서 "같은 값을 두 번 계산하나?"를 항상 확인하세요.

다섯째, 재귀 안에서 리스트를 슬라이싱합니다. f(arr[1:])는 매번 O(n) 복사가 일어나 전체 복잡도가 올라갑니다. 인덱스를 인자로 넘기는 방식으로 바꾸면 복사가 사라집니다.

📝 핵심 요약 + 다음 강 예고

이번 강의 내용을 정리합니다.

#	기억할 것
1	재귀 = 기저 조건 + 재귀 단계
2	기저 조건은 맨 위에, 범위로
3	재귀는 호출 스택으로 동작 — 공간은 깊이
4	파이썬 기본 재귀 한도는 1,000
5	중복 호출은 `lru_cache`로 O(2ⁿ) → O(n)
6	선형 재귀는 대개 반복문으로 대체 가능
7	재귀 안 슬라이싱은 복사 — 인덱스를 넘긴다

지금 해 볼 것은 fib_slow(30)과 fib_fast(30)의 시간을 재 보는 것입니다. 1강에서 배운 time.perf_counter()를 쓰면 됩니다. 데코레이터 한 줄이 만드는 차이를 체감할 수 있습니다.

다음 14강 「분할 정복」에서는 재귀를 전략으로 끌어올립니다. 9강 병합 정렬에서 본 "쪼개고 합치기"를 일반화하고, 거듭제곱을 O(log n)에 계산하는 등 분할 정복이 복잡도를 낮추는 방식을 정리하겠습니다.

재귀

🎯 학습 목표

💡 기저 조건과 재귀 단계

📖 재귀의 비용과 메모이제이션

💻 실전 예제 — 재귀 세 가지

⚠️ 자주 하는 실수

📝 핵심 요약 + 다음 강 예고

📚 참고 자료

관련 주제

코딩 테스트 합격 알고리즘 30강

댓글