[C++] 재귀 함수를 코드로

1이번 챕터의 핵심 메시지

재귀는 자기 자신을 호출하는 함수로, 올바르게 설계하지 않으면 스택 오버플로우가 발생한다. 핵심은 단 두 가지 — 기저 조건(Base Case)과 재귀 호출 단계(Recursive Step)를 명확히 정의하는 것이다. 이 두 가지가 갖춰지면 팩토리얼, DFS, 분할 정복까지 재귀로 자연스럽게 표현할 수 있다.

---

2재귀의 정의와 두 가지 요건

재귀 함수를 구현하려면 반드시 아래 두 가지를 설계해야 한다. 하나라도 빠지면 무한 루프나 스택 오버플로우로 이어진다.

① 재귀 호출 단계

문제 크기 축소

자기 자신을 호출하되, 매번 문제의 크기를 줄여야 한다. 크기가 줄지 않으면 무한 호출로 이어진다.

② 기저 조건 (Base Case)

종료 조건

특정 조건을 만족하면 자기 자신을 더 이상 호출하지 않고 직접 값을 반환해 함수를 종료한다.

기저 조건이 없으면? 함수가 종료되지 않고 계속 스택 프레임이 쌓여 스택 오버플로우(Stack Overflow)가 발생한다. 종료 조건은 반드시 명확하게 정의해야 한다.

---

3재귀 함수 설계 — 팩토리얼 예시

재귀 함수를 설계할 때는 "구현하려는 함수가 이미 있다고 가정"하는 사고방식이 핵심이다. 그러면 현재 문제를 더 작은 문제의 해로 표현하는 데 집중할 수 있다.

1

문제 정의: Fact(N)은 N!을 반환하는 함수라고 가정한다.

2

재귀 호출 단계: Fact(N) = N × Fact(N-1) → 크기 N 문제를 크기 N-1 문제로 축소한다.

3

기저 조건: N이 0 또는 1이면 더 이상 쪼갤 수 없으므로 1을 직접 반환한다.

n! = 1, if n = 0 or n = 1 ← 기저 조건
n! = n × (n−1)!, if n > 1 ← 재귀 호출 단계

int Fact(int N) {
    if (N == 0 || N == 1) return 1;  // 기저 조건
    return N * Fact(N - 1);           // 재귀 호출 단계
}
// Fact(5) → 120

스택 호출 흐름 (N=5)

Fact(5) 호출
  Fact(4) 호출
    Fact(3) 호출
      Fact(2) 호출
        Fact(1) 호출
          Fact(0) 호출
          Fact(0) = 1 반환  ← 기저 조건 도달
        Fact(1) = 1 반환
      Fact(2) = 2 반환
    Fact(3) = 6 반환
  Fact(4) = 24 반환
Fact(5) = 120 반환

---

4수학적 귀납법과 재귀의 관계

재귀 함수 설계는 수학적 귀납법(Mathematical Induction)과 동일한 논리 구조를 가진다. 도미노 효과를 떠올리면 쉽다.

수학적 귀납법

기본 단계: 첫 번째 도미노가 넘어진다.

귀납 단계: k번째가 넘어지면 k+1번째도 반드시 넘어진다.

재귀 함수 설계

기저 조건: 가장 작은 입력(0 or 1)은 직접 답을 반환한다.

재귀 호출 단계: 크기 N 문제를 크기 N-1 문제로 표현한다.

핵심 인사이트: 구현하려는 함수가 이미 있다고 가정하면, 더 작은 문제로 현재 문제를 표현하는 데만 집중할 수 있다. 이것이 재귀 설계의 본질이다.

---

5재귀 함수 동작 시 메모리의 모습

함수가 호출될 때마다 스택 프레임(Stack Frame)이 생성되어 쌓인다. 스택 프레임에는 지역 변수, 매개 변수, 반환 주소가 포함된다. 함수가 종료되면 해당 프레임이 제거되고 이전 호출 위치로 돌아간다.

초기

main()

→

Fact(5) 호출

Fact(5)

main()

→

Fact(3) 호출

Fact(3)

Fact(4)

Fact(5)

main()

→

최대 깊이

Fact(0)

Fact(1)

Fact(2)

Fact(3)

Fact(4)

Fact(5)

main()

주의: 재귀 깊이가 깊어질수록 스택 메모리를 계속 소비한다. 기저 조건에 도달한 후에는 역방향으로 각 프레임이 차례로 제거되며 최종 결과가 계산된다. 호출 깊이를 적절히 제한하지 않으면 스택 오버플로우가 발생할 수 있다.

---

6재귀가 효율적인 경우

대부분의 반복 작업은 반복문으로도 구현할 수 있다. 그럼에도 재귀가 더 자연스럽고 효율적인 경우가 있다.

스택 기반 알고리즘

함수 호출 자체가 LIFO 스택 구조다. DFS(깊이 우선 탐색)을 명시적 스택 없이 재귀로 자연스럽게 구현할 수 있다.

분할 정복 알고리즘

문제를 분할 → 정복 → 결합하는 구조가 재귀와 맞아떨어진다. 병합 정렬, 퀵 정렬이 대표적이다.

DFS — 재귀 vs 반복문 비교

재귀 DFS  간결

void DFS(int node) {
  visited[node] = true;
  cout << node << ' ';
  for (int next : graph[node])
    if (!visited[next])
      DFS(next); // 재귀
}

반복문 DFS  복잡

void DFS(int start) {
  stack<int> s;
  s.push(start);
  visited[start] = true;
  while (!s.empty()) {
    // 역순 탐색 별도 처리...
  }
}

재귀 DFS는 각 함수가 자신과 인접한 노드만 관리하면 되므로 코드가 간결하고 가독성이 높다. 반면 반복문 DFS는 스택 초기화, 삽입, 삭제, 역순 탐색까지 직접 처리해야 해서 코드가 복잡해진다.

---

7재귀 사용 시 주의점 — 피보나치와 메모이제이션

단순 재귀는 중복 호출 문제를 일으킬 수 있다. fibo(6)을 단순 재귀로 계산하면 같은 값을 여러 번 반복 계산해 시간 복잡도가 O(2ⁿ)까지 치솟는다.

단순 재귀  O(2ⁿ)

하나의 함수가 두 개를 호출 → 호출 수가 지수적으로 폭증. fibo(4)가 2번, fibo(3)이 4번 중복 호출된다.

메모이제이션  O(N)

한 번 계산한 결과를 배열에 저장. 이후 동일한 값을 요청받으면 저장된 값을 즉시 반환해 중복 연산을 제거한다.

fibo(40) 계산 — 단순 재귀 vs 메모이제이션 호출 횟수

 

단순 재귀 — O(2ⁿ) 메모이제이션 — O(N)

fibo(40) 기준으로 단순 재귀는 약 3억 3천만 번의 함수 호출이 발생하지만, 메모이제이션 적용 시 단 79번만 호출된다. 메모이제이션 하나만으로 수백만 배의 성능 차이가 생긴다.

// 메모이제이션을 적용한 피보나치
vector<int> memo(1000, -1);

int fibo(int n) {
    if (n == 1 || n == 2) return 1;
    if (memo[n] != -1) return memo[n];  // 이미 계산됨 → 즉시 반환
    memo[n] = fibo(n - 1) + fibo(n - 2);
    return memo[n];
}

---

8재귀 예시 — 지수 연산의 최적화

X의 N승을 단순 재귀로 구현하면 O(N)이다. N이 짝수일 때 문제 크기를 절반으로 줄이는 분할 정복을 적용하면 O(log N)으로 개선할 수 있다.

기본 재귀  O(N)

매번 1씩 줄여가며 N번 호출. N이 클수록 호출 횟수가 선형으로 증가한다.

분할 정복  O(log N)

짝수면 절반으로 분할해 제곱. 홀수면 하나 더 곱함. 호출 횟수가 log N으로 급감한다.

pow(2, N) 계산 — 재귀 호출 횟수 비교

 

기본 재귀 — O(N) 분할 정복 — O(log N)

// 분할 정복을 활용한 효율적인 X의 N승 계산
double pow(double X, int N) {
    if (N == 0) return 1;
    double half = pow(X, N / 2);
    if (N % 2 == 0)
        return half * half;        // 짝수: (X^(N/2))²
    else
        return half * half * X;    // 홀수: (X^(N/2))² × X
}
// pow(2.0, 10) = 1024

---

9한눈에 보는 정리 — 재귀 vs 반복문

특성	재귀 함수	반복문
메모리 사용	스택 프레임 누적 → 오버플로우 위험	스택 메모리 사용 없음 → 효율적
실행 속도	함수 호출 오버헤드 → 상대적으로 느림	함수 호출 없음 → 일반적으로 빠름
가독성	재귀 구조 문제에서 간결하고 직관적	단순 반복 작업에서 직관적
변수 사용	상태 변수 불필요, 코드 간결	상태 유지 변수 다수 필요
무한 반복 시	스택 오버플로우 발생	CPU 점유 → 시스템 부하
적합한 상황	DFS, 분할 정복, 트리/그래프 탐색	단순 집계, 선형 순회, 성능 중시

---

10오늘의 회고

이번 챕터에서 가장 인상 깊었던 건 "구현하려는 함수가 이미 있다고 가정하라"는 사고방식이었다. 처음엔 순환 논리처럼 느껴졌지만, 수학적 귀납법과 연결해서 생각하니 오히려 명확하게 이해됐다. 재귀를 설계할 때 기저 조건을 먼저 잡고, 그다음 현재 문제를 더 작은 문제로 표현하는 순서로 접근하면 훨씬 수월하다는 것도 배웠다.

피보나치의 단순 재귀가 O(2ⁿ)이 되는 이유를 트리 구조로 직접 시각화하니 명확하게 와닿았고, 메모이제이션 하나만으로 O(N)으로 줄어드는 것이 생각보다 훨씬 강력하게 느껴졌다. 앞으로 재귀 문제를 만나면 ① 중복 호출이 발생하는 구조인지 확인하고, 그렇다면 메모이제이션을 바로 적용하는 습관을 들여야겠다.