재귀 (Recursion)

정의

재귀 (Recursion) 는 함수가 자기 자신을 호출하는 프로그래밍 기법. base case (종료 조건) 와 recursive case (재귀 단계) 로 구성되며, 복잡한 문제를 더 작은 부분 문제로 분해한다.

재귀는 분할정복, 동적 계획법, 백트래킹, 트리 순회 의 기초.

문제 상황과 동기

factorial, fibonacci, 하노이 탑, 트리 순회, 조합 생성 같은 자기 유사 구조 문제.

• naive (반복문): factorial 은 for i in 1..N 가능하지만, 트리 순회, 조합 같은 경우 깊이가 가변이라 반복문으로 표현 불가능하거나 매우 복잡.
• recursion (재귀): 문제를 “작은 문제 + 합성” 으로 정의. 코드가 수학 정의와 1:1.

핵심 통찰: 문제가 자기 자신의 부분 문제로 표현되면 재귀. 예: factorial(N) = N * factorial(N-1), fib(N) = fib(N-1) + fib(N-2).

함수형 프로그래밍, 수학 귀납법, 점화식의 직접 구현.

시각화

핵심 아이디어

재귀 함수는 반드시 다음 두 요소를 포함:

1. base case: 재귀를 멈추는 조건. 없으면 무한 재귀 → stack overflow.
2. recursive case: 자기 자신을 더 작은 입력으로 호출.

function f(n):
    if base_condition(n):
        return base_value
    return combine(f(smaller(n)))

invariant: 호출 스택의 각 프레임은 부분 문제. 스택이 base case 에 도달하면 값을 반환하며 unwinding.

대표 예시:

int factorial(int n) {
    if (n == 0) return 1;         // base case
    return n * factorial(n - 1);  // recursive case
}

호출 흐름: factorial(4) → 4 * factorial(3) → 4 * 3 * factorial(2) → ... → 4 * 3 * 2 * 1 * 1.

알고리즘

Factorial

factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

Fibonacci (naive)

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

O(2^N) 중복 호출. 메모이제이션 또는 DP 로 O(N).

조합 생성 (재귀)

choose(idx, chosen, K):
    if len(chosen) == K:
        print(chosen)
        return
    if idx == N:
        return
    choose(idx+1, chosen + [a[idx]], K)  # 선택
    choose(idx+1, chosen, K)             # 건너뜀

구현

// factorial 재귀
#include <bits/stdc++.h>
using namespace std;
long long factorial(int n) {
  if (n == 0) return 1;
  return n * factorial(n - 1);
}
int main() {
  int n; cin >> n;
  cout << factorial(n) << "\n";
}

# factorial 재귀
def factorial(n):
  if n == 0:
      return 1
  return n * factorial(n - 1)
​
n = int(input())
print(factorial(n))

// factorial 재귀
import java.util.*;
public class Main {
  static long factorial(int n) {
      if (n == 0) return 1;
      return n * factorial(n - 1);
  }
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      System.out.println(factorial(n));
  }
}

4

24

0

1

복잡도

재귀 깊이 = 스택 프레임 수. C++ / Java 는 보통 10^4~10^6, Python 은 기본 1000 (늘릴 수 있음).

재귀 vs 반복문

꼬리 재귀 (tail recursion): 재귀 호출이 함수 마지막 연산. 일부 컴파일러가 반복문으로 변환.

int factorial_tail(int n, int acc = 1) {
    if (n == 0) return acc;
    return factorial_tail(n - 1, n * acc);  // tail call
}

변형

1. 메모이제이션

중복 호출 결과를 캐싱. fib(N) 이 O(2^N) → O(N).

map<int, long long> memo;
long long fib(int n) {
    if (n <= 1) return n;
    if (memo.count(n)) return memo[n];
    return memo[n] = fib(n-1) + fib(n-2);
}

2. 분할정복

문제를 여러 부분으로 나누고 재귀. 병합 정렬, 퀵 정렬.

merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

3. 백트래킹

재귀로 모든 경우를 탐색하되, 조건 위반시 조기 종료. N-Queen, 순열 생성.

void backtrack(int depth) {
    if (depth == N) { process(); return; }
    for (int i = 0; i < N; i++) {
        if (!is_valid(i)) continue;
        choose(i);
        backtrack(depth + 1);
        unchoose(i);
    }
}

함정

1. base case 누락

int fib(int n) {
    return fib(n-1) + fib(n-2);  // 무한 재귀
}

반드시 if (n <= 1) return n; 같은 종료 조건.

2. 스택 오버플로우

재귀 깊이가 10^4 초과하면 위험. N=10^6 같은 입력은 재귀 대신 반복문.

Python:

import sys
sys.setrecursionlimit(10**6)  # 재귀 한계 늘리기

C++ / Java: 컴파일 옵션 또는 스레드 스택 크기 조정.

3. 중복 계산 (exponential blow-up)

naive fib(N) 은 O(2^N). N=40 이면 10억 번 호출. 메모이제이션 필수.

4. 값 전달 vs 참조 전달

void rec(vector<int> v) {  // 복사 → 느림
    rec(v);
}

void rec(vector<int>& v) {  // 참조 → 빠름
    rec(v);
}

큰 배열은 참조로.

BOJ 연습 문제

참고

• 분할정복
• 동적 계획법
• 백트래킹
• 메모이제이션
• 트리