재귀 — 문제를 자기 자신으로 푼다

재귀는 같은 구조의 더 작은 문제를 자기 자신을 호출해 푸는 기법이다. 반복문이 “어떻게” 처리할지를 명시한다면, 재귀는 “무엇이” 해결책인지를 정의한다.

재귀란 무엇인가

재귀(Recursion) 란 함수가 자기 자신을 호출하여 문제를 해결하는 기법이다. 핵심 아이디어는 큰 문제를 더 작은 동일한 구조의 하위 문제로 분해하는 것이다.

올바른 재귀 함수는 반드시 두 부분을 포함해야 한다.

구성 요소	설명
Base Case (기저 사례)	더 이상 재귀 호출 없이 직접 답을 반환하는 경우
Recursive Case (재귀 사례)	문제를 더 작은 하위 문제로 분해하고 재귀 호출

Base Case 없는 재귀는 무한히 자기 자신을 호출하다 스택 오버플로(Stack Overflow) 로 종료된다. Recursive Case가 문제를 실제로 더 작게 만들지 않아도 같은 결과가 발생한다.

---

팩토리얼

$$n! = n \times (n-1) \times (n-2) \times \cdots \times 1, \quad 0! = 1$$

이를 재귀적으로 정의하면:

$$n! = \begin{cases} 1 & n = 0 \\ n \times (n-1)! & n \ge 1 \end{cases}$$

아래 구현은 $n \ge 0$을 전제로 한다 (음수 입력은 Base Case에 닿지 못해 무한 재귀에 빠지므로, 방어가 필요하면 if n < 0: raise ValueError를 앞에 둔다).

def factorial(n: int) -> int:
    # Base Case
    if n == 0:
        return 1
    # Recursive Case
    return n * factorial(n - 1)

실행 흐름 (factorial(4)):

factorial(4)
  = 4 * factorial(3)
        = 3 * factorial(2)
              = 2 * factorial(1)
                    = 1 * factorial(0)
                                = 1       ← Base Case
                    = 1 * 1 = 1
              = 2 * 1 = 2
        = 3 * 2 = 6
  = 4 * 6 = 24

복잡도 분석:

점화식: $T(n) = T(n-1) + O(1)$

이를 전개하면:

$$T(n) = T(n-1) + c = T(n-2) + 2c = \cdots = T(0) + nc = O(n)$$

시간 복잡도: $O(n)$, 공간 복잡도: $O(n)$.

공간 복잡도가 $O(n)$인 이유는 콜 스택(call stack) 때문이다. 함수가 자기 자신을 호출하면, 아직 끝나지 않은 각 호출의 지역 상태(매개변수, 돌아갈 위치 등)가 스택에 차곡차곡 쌓인다. factorial(n)은 Base Case에 닿기까지 $n$단계가 동시에 쌓이므로 깊이가 $O(n)$이다. 이 깊이가 한도를 넘으면 스택 오버플로가 발생한다.

---

수학적 귀납법으로 재귀 증명하기

재귀 알고리즘의 구조는 수학적 귀납법의 구조와 완벽히 대응한다. 이 대응을 이해하면, 재귀 알고리즘의 올바름을 엄밀히 증명할 수 있다.

수학적 귀납법	재귀 알고리즘
기저 사례 (Base Case)	Base Case: 직접 답을 반환
귀납 가정 (Inductive Hypothesis)	“하위 재귀 호출이 올바르다”는 가정
귀납 단계 (Inductive Step)	Recursive Case: 하위 결과를 조합해 현재 답 생성

재귀 알고리즘의 올바름을 증명하는 핵심 통찰은 이것이다.

귀납 가정을 신뢰하라. factorial(n-1)이 올바른 결과를 반환한다고 가정한다. 그 위에서 현재 단계가 올바른지를 보이면 된다.

예제: factorial(n)의 올바름 증명

명제 $P(n)$: factorial(n)은 $n!$을 올바르게 반환한다. ($n \ge 0$)

Base Case ($P(0)$): factorial(0)은 1을 반환한다. $0! = 1$이므로 성립.

Inductive Step: $P(k)$가 참, 즉 factorial(k) $= k!$이라고 가정한다. ($k \ge 0$)

factorial(k+1)을 실행하면 $(k+1) \ge 1$이므로 Recursive Case가 수행된다.

factorial(k+1)
  = (k+1) * factorial(k)     ← 코드의 return n * factorial(n-1)
  = (k+1) * k!               ← 귀납 가정: factorial(k) = k!
  = (k+1)!                   ← 팩토리얼 정의

따라서 $P(k+1)$이 참이다. (수학적) 귀납법에 의해 모든 $n \ge 0$에 대해 $P(n)$이 성립한다. $\square$ 팩토리얼은 바로 앞 값 하나에만 의존하므로 약한 귀납법으로 충분하다. 여러 개의 더 작은 하위 문제에 의존하는 경우(아래 이진 탐색)에는 강한 귀납법이 필요하다.

예제: binary_search의 올바름 증명 (강한 귀납법)

이진 탐색처럼 문제를 절반으로 쪼개는 분할 정복 알고리즘은, 반복문으로 구현하든 재귀로 구현하든 하위 문제 크기에 대한 귀납법으로 똑같이 증명할 수 있다. 여기서는 강한 귀납법을 사용한다. 탐색 범위의 크기 $m = \text{right} - \text{left} + 1$에 대한 귀납법이다.

명제 $P(m)$: 크기 $m$의 정렬된 부분 배열에서 이진 탐색은 올바르게 동작한다.

Base Case ($m = 0$): left > right이면 루프 진입 없이 -1 반환. target이 없으므로 올바르다.

Inductive Step: 크기 $< m$인 모든 배열에서 올바르다고 가정한다. 크기 $m$인 배열에서:

• arr[mid] == target → 올바르게 반환.
• arr[mid] < target → 오른쪽 절반(크기 $\lfloor m/2 \rfloor < m$)에서 탐색. 귀납 가정에 의해 올바르다.
• arr[mid] > target → 왼쪽 절반(크기 $\lfloor (m-1)/2 \rfloor < m$)에서 탐색. 귀납 가정에 의해 올바르다.

모든 경우에 올바르므로 $P(m)$이 성립한다. $\square$

---

피보나치와 지수적 폭발

$$F(n) = \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ F(n-1) + F(n-2) & n \ge 2 \end{cases}$$

def fib_naive(n: int) -> int:
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

직관적으로 깔끔해 보이지만, 이 구현은 심각한 문제를 갖는다. fib(5)를 계산해 보자.

fib(5)
  fib(4)
    fib(3)
      fib(2)
        fib(1) = 1
        fib(0) = 0
      fib(1) = 1
    fib(2)         ← fib(2) 중복 계산!
      fib(1) = 1
      fib(0) = 0
  fib(3)           ← fib(3) 중복 계산!
    fib(2)
      fib(1) = 1
      fib(0) = 0
    fib(1) = 1

위 트리에서 보듯 같은 하위 문제가 여러 경로에서 거듭 호출된다. fib(3)은 2번, fib(2)는 3번 다시 계산된다. 입력이 커질수록 이런 중복이 기하급수적으로 늘어나는 것이 단순 재귀의 핵심 문제다.

fib(n)을 계산하는 데 필요한 호출 횟수를 $T(n)$이라 하면:

$$T(n) = T(n-1) + T(n-2) + O(1)$$

$T(n)$은 피보나치 수열 자체와 같은 성장률을 가지며, $T(n) = O(\phi^n)$ ($\phi \approx 1.618$, 황금비)이다. $O(\phi^n)$과 $O(2^n)$은 정확히 같은 차수는 아니지만, 둘 다 지수 함수 꼴로 폭발한다는 점에서 같은 계열이다.

$n = 50$일 때: 호출 횟수는 $\phi^{50}$ 규모(상한으로 보면 $2^{50} \approx 10^{15}$)에 이른다. 호출 한 번의 비용과 실행 환경에 따라 달라지지만, 이 정도면 단순 재귀로는 현실적인 시간 안에 끝나지 않는다.

해결책: 메모이제이션

이미 계산한 결과를 저장해 두고 재사용한다.

def fib_memo(n: int, memo: dict = None) -> int:
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]        # 캐시 히트
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

$k \ge 2$인 각 $F(k)$는 정확히 한 번만 계산되고, 두 번째부터는 memo에서 바로 반환된다 (Base Case인 $F(0)$, $F(1)$은 캐시에 저장하지 않으므로 여러 번 도달할 수 있지만, 상수 시간이라 전체 복잡도에는 영향이 없다). 결국 중복되는 큰 하위 문제를 한 번씩만 계산하므로 시간 복잡도: $O(n)$, 공간 복잡도: $O(n)$.

# Python 표준 라이브러리 활용
from functools import lru_cache

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

이렇게 재귀 + 캐시로 위에서 아래로 푸는 방식을 탑다운(top-down) 메모이제이션이라 한다. 같은 점화식을 작은 값부터 배열에 채워 올라가며 반복문으로 풀면 바텀업(bottom-up) 동적 프로그래밍이 된다. 둘은 계산하는 하위 문제 집합이 같아 시간 복잡도도 같으며, 재귀와 반복이라는 표현 방식만 다르다.

---

하노이의 탑

세 개의 기둥(A, B, C)과 크기가 모두 다른 $n$개의 원판이 있다. 처음에 모든 원판이 A 기둥에 크기 순으로 쌓여 있다.

규칙:

1. 한 번에 원판 하나만 이동할 수 있다.
2. 큰 원판을 작은 원판 위에 올릴 수 없다.

A에서 C로 모든 원판을 옮기는 알고리즘은 다음과 같다 (원판이 최소 하나 있다고 보고 $n \ge 1$을 전제한다).

$$\text{hanoi}(n, A \to C) = \text{hanoi}(n-1, A \to B) + \text{move}(A \to C) + \text{hanoi}(n-1, B \to C)$$

def hanoi(n: int, source: str, target: str, aux: str) -> None:
    """
    n개의 원판을 source에서 target으로 aux를 이용해 옮긴다.
    """
    if n == 1:
        print(f"원판 1: {source} → {target}")
        return
    # 1단계: 위의 n-1개를 보조 기둥으로 이동
    hanoi(n - 1, source, aux, target)
    # 2단계: 가장 큰 원판을 목적지로 이동
    print(f"원판 {n}: {source} → {target}")
    # 3단계: n-1개를 보조 기둥에서 목적지로 이동
    hanoi(n - 1, aux, target, source)

# 실행
hanoi(3, 'A', 'C', 'B')

$n = 2$의 실제 이동 순서를 따라가 보면 재귀 구조가 분명해진다. hanoi(2, A→C)는 (1) 위의 1개를 보조 기둥 B로 옮기고 (2) 큰 원판을 C로 옮긴 뒤 (3) B의 1개를 다시 C로 옮긴다.

원판 1: A → B      (1단계: hanoi(1, A→B))
원판 2: A → C      (2단계: 가장 큰 원판 이동)
원판 1: B → C      (3단계: hanoi(1, B→C))

총 3번, 즉 $2^2 - 1 = 3$번 이동한다.

점화식:

$$T(n) = 2T(n-1) + 1, \quad T(1) = 1$$

전개하면:

$$T(n) = 2T(n-1) + 1 = 2(2T(n-2) + 1) + 1 = 4T(n-2) + 3 = \cdots = 2^{n-1}T(1) + (2^{n-1} - 1) = 2^n - 1$$ $$T(n) = \Theta(2^n)$$

$n = 64$일 때 필요한 이동 횟수: $2^{64} - 1 \approx 1.8 \times 10^{19}$회. 초당 1회 이동한다면 약 5800억 년이 걸린다.

$2^n - 1$보다 적게는 못 옮긴다

여기까지는 이 알고리즘이 $2^n - 1$번 움직인다는 사실만 보였다. 더 영리한 방법이 있을 가능성은 아직 배제되지 않았다. 최소성을 보이려면 방향을 뒤집어, 어떤 방법이든 그보다 적게는 안 된다는 하한을 세워야 한다.

$n$개를 옮기는 데 필요한 최소 이동 횟수를 $M(n)$이라 하자. $M(0) = 0$이다.

$n \ge 1$일 때, 가장 큰 원판은 반드시 한 번 이상 움직인다. A에서 출발해 C에 도착해야 하기 때문이다. 그 첫 이동 직전의 상태를 보자. 가장 큰 원판은 어떤 원판 위에도 올릴 수 없으므로 목적지 기둥이 비어 있어야 하고, 자기가 놓인 기둥에서도 맨 아래이면서 위에 아무것도 없어야 한다. 기둥은 셋뿐이므로 나머지 $n-1$개는 남은 기둥 하나에 모두 모여 있다. 그 상태를 만드는 데 최소 $M(n-1)$번이 든다.

같은 논리를 가장 큰 원판의 마지막 이동에 적용한다. 그 이동으로 가장 큰 원판이 C에 자리 잡고 이후 다시 움직이지 않으므로, 이동 직후 나머지 $n-1$개는 다시 한 기둥에 모여 있다. 이들이 전부 C로 가야 하니 최소 $M(n-1)$번이 더 든다.

두 구간은 겹치지 않는다. 하나는 가장 큰 원판의 첫 이동 이전이고, 다른 하나는 마지막 이동 이후다. 여기에 가장 큰 원판 자신의 이동 최소 1번을 더하면

$$M(n) \ge 2M(n-1) + 1$$

이고, $M(0) = 0$에서 귀납으로 $M(n) \ge 2^n - 1$이 나온다. 한편 위 알고리즘이 정확히 $2^n - 1$번에 해내므로 $M(n) \le 2^n - 1$이다. 두 부등호를 합치면

$$M(n) = 2^n - 1$$

이다. 이제 “이보다 더 줄일 수 없다”고 말해도 된다.

---

재귀 트리 분석

재귀 호출의 구조를 트리로 시각화하면 총 수행 시간을 직관적으로 분석할 수 있다.

merge sort의 점화식: $T(n) = 2T(n/2) + O(n)$

• 트리의 깊이: $\log_2 n$
• 각 레벨의 총 작업량: $n$
• 전체 작업량: $n \times \log_2 n = O(n \log n)$

여기서 “깊이 × 레벨당 작업량”으로 단순히 곱할 수 있는 것은 모든 레벨의 총 작업량이 $n$으로 일정하기 때문이다. 만약 레벨마다 작업량이 다르면 각 레벨을 더해야 하며, 이를 일반화한 도구가 바로 다음에 볼 마스터 정리다.

---

마스터 정리

$a \ge 1$, $b > 1$인 상수에 대해 점화식이 다음 형태이면:

$$T(n) = aT\!\left(\frac{n}{b}\right) + f(n)$$

마스터 정리(Master Theorem)로 $T(n)$의 점근적 해를 구할 수 있다.

직관적 이해: $n^{\log_b a}$는 재귀 트리에서 리프 노드의 총 비용이고, $f(n)$은 각 레벨의 분할/병합 비용이다. 둘 중 어느 쪽이 지배적인가에 따라 해가 결정된다.

Case 1: 리프 비용이 지배

$$f(n) = O(n^{\log_b a - \varepsilon}), \quad \varepsilon > 0 \implies T(n) = \Theta(n^{\log_b a})$$

Case 2: 균형 (동등)

$$f(n) = \Theta(n^{\log_b a}) \implies T(n) = \Theta(n^{\log_b a} \cdot \log n)$$

Case 3: 분할/병합 비용이 지배

$$f(n) = \Omega(n^{\log_b a + \varepsilon}), \quad \varepsilon > 0,\; af(n/b) \le cf(n) \implies T(n) = \Theta(f(n))$$

마스터 정리 적용 예시

점화식	$a$	$b$	$n^{\log_b a}$	$f(n)$	케이스	결과
$T(n) = 2T(n/2) + n$	2	2	$n^1 = n$	$n$	Case 2	$\Theta(n \log n)$
$T(n) = 4T(n/2) + n$	4	2	$n^2$	$n$	Case 1	$\Theta(n^2)$
$T(n) = T(n/2) + n$	1	2	$n^0 = 1$	$n$	Case 3	$\Theta(n)$
$T(n) = 9T(n/3) + n^2$	9	3	$n^2$	$n^2$	Case 2	$\Theta(n^2 \log n)$
$T(n) = 2T(n/2) + n^2$	2	2	$n$	$n^2$	Case 3	$\Theta(n^2)$

merge sort 검증: $a=2$, $b=2$ → $n^{\log_2 2} = n^1 = n = f(n)$ → Case 2 → $T(n) = \Theta(n \log n)$. 성립.

---

재귀 vs 반복

재귀와 반복문은 표현력이 동등하다. 모든 재귀는 반복문으로 변환할 수 있고, 그 역도 성립한다. 구체적으로는, 콜 스택이 하던 일을 명시적 스택(자료구조) 으로 직접 관리하면 어떤 재귀든 반복문으로 바꿀 수 있다.

비교 항목	재귀	반복
코드 간결성	문제 구조가 재귀적이면 훨씬 간결	상태 관리를 직접 해야 함
가독성	수학적 정의와 1:1 대응	명시적 루프 제어
공간 복잡도	콜 스택 $O(d)$ ($d$: 재귀 깊이)	경우에 따라 $O(1)$ 또는 $O(d)$ (아래 참고)
적합한 문제	트리, 그래프, 분할 정복	단순 반복, 배열 순회
주의사항	스택 오버플로 위험	—

재귀가 빛나는 문제는 문제 자체가 재귀적 구조를 가질 때다. 트리 순회, 분할 정복, 동적 프로그래밍의 원형은 재귀로 표현하는 것이 가장 자연스럽다.