재귀 함수 마스터하기 – 개념부터 구현까지 완벽 가이드

재귀 함수 마스터하기는 프로그래밍에서 가장 중요한 개념 중 하나입니다. 재귀 함수란 함수가 자기 자신을 호출하는 방식으로 문제를 해결하는 기법으로, 복잡한 문제를 더 작은 하위 문제로 분해하여 해결할 수 있습니다. 트리 순회, 그래프 탐색, 동적 프로그래밍 등 다양한 알고리즘에서 핵심적으로 사용되며, 코딩테스트와 실무에서 필수적인 기술입니다. 이 가이드에서는 재귀 함수의 기본 개념부터 고급 최적화 기법까지 체계적으로 학습하여 재귀 함수를 완벽하게 마스터할 수 있도록 도와드립니다.

1. 재귀 함수의 개념과 필요성

재귀 함수는 함수 내부에서 자기 자신을 호출하는 프로그래밍 기법입니다. 수학의 귀납법과 유사한 원리로 작동하며, 큰 문제를 동일한 구조의 작은 문제로 분해하여 해결합니다. 재귀 함수는 반복문으로 구현하기 어려운 복잡한 로직을 간결하고 직관적으로 표현할 수 있다는 장점이 있습니다.

재귀 함수는 크게 두 가지 요소로 구성됩니다. 첫째, Base Case(기저 조건)는 재귀 호출을 멈추는 조건으로, 이것이 없으면 무한 루프에 빠지게 됩니다. 둘째, Recursive Case(재귀 조건)는 문제를 더 작은 하위 문제로 분해하여 자기 자신을 호출하는 부분입니다. 이 두 요소가 올바르게 구현되어야 재귀 함수가 정상적으로 동작합니다.

2. 재귀 함수의 동작 원리

재귀 함수의 동작 원리를 이해하기 위해서는 콜 스택(Call Stack)의 개념을 알아야 합니다. 함수가 호출될 때마다 해당 함수의 실행 컨텍스트가 스택에 쌓이고, 함수가 종료되면 스택에서 제거됩니다. 재귀 함수는 자기 자신을 반복적으로 호출하므로 콜 스택에 여러 개의 함수 프레임이 쌓이게 됩니다.

예를 들어, 팩토리얼 함수 factorial(5)를 호출하면 다음과 같은 과정을 거칩니다:

1. factorial(5) 호출 → 5 * factorial(4) 계산 필요
2. factorial(4) 호출 → 4 * factorial(3) 계산 필요
3. factorial(3) 호출 → 3 * factorial(2) 계산 필요
4. factorial(2) 호출 → 2 * factorial(1) 계산 필요
5. factorial(1) 호출 → Base Case 도달, 1 반환
6. 역순으로 스택을 풀면서 결과 계산: 2*1=2, 3*2=6, 4*6=24, 5*24=120

이처럼 재귀 함수는 Base Case에 도달할 때까지 호출을 계속하고, 그 후 스택을 거슬러 올라가며 결과를 계산합니다. 이를 Winding(감기)과 Unwinding(풀기) 과정이라고 합니다. 재귀의 깊이가 깊어질수록 메모리 사용량이 증가하므로, 스택 오버플로우를 방지하기 위한 적절한 Base Case 설정이 중요합니다.

3. 시간 및 공간 복잡도 분석

재귀 함수의 복잡도 분석은 문제의 특성에 따라 달라집니다. 시간 복잡도는 재귀 호출이 몇 번 발생하는지와 각 호출에서 수행되는 작업량에 의해 결정됩니다.

팩토리얼의 경우 n번의 재귀 호출이 발생하고 각 호출마다 O(1) 작업을 수행하므로 시간 복잡도는 O(n)입니다. 하지만 피보나치 수열을 순수 재귀로 구현하면 fib(n) = fib(n-1) + fib(n-2)로 인해 중복 계산이 발생하여 시간 복잡도가 O(2^n)으로 기하급수적으로 증가합니다.

공간 복잡도는 콜 스택의 깊이에 의해 결정됩니다. 재귀 깊이가 n이면 최대 n개의 함수 프레임이 스택에 쌓이므로 공간 복잡도는 O(n)입니다. 반복문으로 구현하면 O(1)의 공간만 사용하므로, 메모리 효율성 측면에서는 반복문이 유리할 수 있습니다. 하지만 메모이제이션이나 꼬리 재귀 최적화를 사용하면 재귀 함수의 효율성을 크게 개선할 수 있습니다.

4. 단계별 구현 과정

4.1 기본 재귀 – 팩토리얼

가장 기본적인 재귀 함수 예제인 팩토리얼부터 시작하겠습니다:

// 팩토리얼: n! = n × (n-1) × ... × 2 × 1
function factorial(n) {
  // Base Case: 0! = 1, 1! = 1
  if (n <= 1) {
    return 1;
  }
  
  // Recursive Case: n! = n × (n-1)!
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 120
console.log(factorial(0)); // 1

4.2 중급 재귀 - 피보나치 수열

피보나치 수열은 재귀의 비효율성을 보여주는 좋은 예시입니다:

// 순수 재귀 구현 (비효율적 - O(2^n))
function fibonacciNaive(n) {
  if (n <= 1) {
    return n;
  }
  return fibonacciNaive(n - 1) + fibonacciNaive(n - 2);
}

// 메모이제이션을 활용한 최적화 (O(n))
function fibonacciMemo(n, memo = {}) {
  if (n <= 1) {
    return n;
  }
  
  // 이미 계산된 값이 있으면 재사용
  if (memo[n]) {
    return memo[n];
  }
  
  // 계산 결과를 메모에 저장
  memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
  return memo[n];
}

console.log(fibonacciMemo(40)); // 102334155 (빠르게 계산)

4.3 고급 재귀 - 이진 트리 순회

재귀는 트리 구조 탐색에서 가장 강력한 도구입니다:

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// 중위 순회 (Inorder: Left - Root - Right)
function inorderTraversal(root, result = []) {
  if (root === null) {
    return result;
  }
  
  inorderTraversal(root.left, result);  // 왼쪽 서브트리
  result.push(root.value);               // 현재 노드
  inorderTraversal(root.right, result);  // 오른쪽 서브트리
  
  return result;
}

// 트리 생성 및 테스트
const root = new TreeNode(4);
root.left = new TreeNode(2);
root.right = new TreeNode(6);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(3);

console.log(inorderTraversal(root)); // [1, 2, 3, 4, 6]

4.4 백트래킹 - 순열 생성

재귀는 백트래킹 알고리즘의 핵심입니다:

// 배열의 모든 순열 생성
function permutations(arr) {
  const result = [];
  
  function backtrack(current, remaining) {
    // Base Case: 남은 요소가 없으면 순열 완성
    if (remaining.length === 0) {
      result.push([...current]);
      return;
    }
    
    // Recursive Case: 각 요소를 선택하여 재귀 호출
    for (let i = 0; i < remaining.length; i++) {
      const next = remaining[i];
      const newRemaining = remaining.filter((_, idx) => idx !== i);
      
      current.push(next);
      backtrack(current, newRemaining);
      current.pop(); // 백트래킹: 선택 취소
    }
  }
  
  backtrack([], arr);
  return result;
}

console.log(permutations([1, 2, 3]));
// [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

5. 재귀 함수 최적화 방법

재귀 함수 마스터하기의 핵심은 효율적인 최적화 기법을 아는 것입니다. 세 가지 주요 최적화 방법을 소개합니다:

5.1 메모이제이션(Memoization)

이미 계산한 결과를 저장하여 중복 계산을 방지합니다. 동적 프로그래밍의 하향식 접근법으로, 해시맵이나 배열에 결과를 캐싱합니다.

5.2 꼬리 재귀 최적화(Tail Recursion)

재귀 호출이 함수의 마지막 작업일 때, 컴파일러가 스택 프레임을 재사용하여 공간 복잡도를 O(1)로 줄일 수 있습니다:

// 일반 재귀 (스택 사용)
function factorialNormal(n) {
  if (n <= 1) return 1;
  return n * factorialNormal(n - 1); // 재귀 후 곱셈 연산 필요
}

// 꼬리 재귀 (최적화 가능)
function factorialTail(n, accumulator = 1) {
  if (n <= 1) return accumulator;
  return factorialTail(n - 1, n * accumulator); // 마지막 작업이 재귀 호출
}

5.3 반복문 변환

모든 재귀는 반복문으로 변환 가능하며, 스택 오버플로우 위험이 있는 경우 반복문 사용을 고려해야 합니다.

6. 실전 활용 예제

재귀 함수는 다양한 실전 문제에 활용됩니다:

• 깊이 우선 탐색(DFS): 그래프와 트리 탐색
• 분할 정복: 병합 정렬, 퀵 정렬, 이진 탐색
• 동적 프로그래밍: 최장 공통 부분수열(LCS), 배낭 문제
• 백트래킹: N-Queen, 스도쿠 해결, 조합 생성
• 트리 문제: 이진 트리의 높이, 경로 합, 최소 공통 조상

재귀 함수 마스터하기는 알고리즘 문제 해결 능력을 크게 향상시킵니다. Base Case와 Recursive Case를 명확히 정의하고, 필요시 메모이제이션으로 최적화하며, 스택 깊이를 고려하여 구현한다면 복잡한 문제도 우아하게 해결할 수 있습니다.