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

1. 알고리즘 소개 및 개념

재귀 함수 마스터하기는 프로그래밍에서 가장 중요한 개념 중 하나입니다. 재귀(Recursion)란 함수가 자기 자신을 호출하는 프로그래밍 기법으로, 복잡한 문제를 더 작은 하위 문제로 분할하여 해결하는 분할 정복(Divide and Conquer) 전략의 핵심입니다. 재귀 함수는 베이스 케이스(Base Case)와 재귀 케이스(Recursive Case)로 구성되며, 베이스 케이스는 재귀 호출을 종료하는 조건이고, 재귀 케이스는 문제를 더 작은 단위로 나누어 자기 자신을 호출하는 부분입니다. 트리 순회, 그래프 탐색, 동적 프로그래밍 등 다양한 알고리즘에서 재귀는 필수적으로 사용됩니다.

2. 동작 원리 상세 설명

재귀 함수의 동작 원리는 콜 스택(Call Stack)을 기반으로 합니다. 함수가 호출될 때마다 현재 실행 컨텍스트가 스택에 쌓이고, 함수가 종료되면 스택에서 제거됩니다. 재귀 호출이 발생하면 새로운 함수 호출이 스택에 추가되며, 베이스 케이스에 도달할 때까지 이 과정이 반복됩니다. 베이스 케이스에 도달하면 가장 최근에 호출된 함수부터 역순으로 반환되면서 결과가 계산됩니다. 예를 들어, 팩토리얼 계산에서 factorial(5)는 5 * factorial(4)를 호출하고, factorial(4)는 4 * factorial(3)을 호출하는 식으로 factorial(1)까지 진행됩니다. factorial(1)이 1을 반환하면 역순으로 2 * 1 = 2, 3 * 2 = 6, 4 * 6 = 24, 5 * 24 = 120이 계산되어 최종 결과가 도출됩니다. 이러한 스택 기반 실행 방식은 재귀의 메모리 사용과 성능에 직접적인 영향을 미칩니다.

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

시간 복잡도: 재귀 함수의 시간 복잡도는 재귀 호출 횟수와 각 호출에서 수행되는 작업량에 따라 결정됩니다. 단순 재귀(팩토리얼)는 O(n), 이진 트리 재귀(피보나치)는 O(2^n), 분할 정복(병합 정렬)은 O(n log n)의 복잡도를 가집니다. 피보나치 수열의 순수 재귀 구현은 중복 계산으로 인해 지수 시간이 소요되지만, 메모이제이션을 적용하면 O(n)으로 개선됩니다.

공간 복잡도: 재귀 함수의 공간 복잡도는 주로 콜 스택의 깊이에 의해 결정됩니다. 최대 재귀 깊이가 n이면 O(n)의 스택 공간이 필요합니다. 꼬리 재귀 최적화(Tail Call Optimization)를 지원하는 언어에서는 O(1) 공간으로 최적화할 수 있지만, JavaScript는 일부 엔진에서만 제한적으로 지원합니다. 깊은 재귀는 스택 오버플로우를 유발할 수 있어 반복문으로 전환하거나 최적화가 필요합니다.

4. 단계별 구현 과정

4.1 기본 재귀 – 팩토리얼

// 베이스 케이스와 재귀 케이스를 명확히 구분
function factorial(n) {
  // 베이스 케이스: 재귀 종료 조건
  if (n <= 1) return 1;
  
  // 재귀 케이스: 문제를 더 작은 단위로 분할
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 120
// 실행 흐름: 5 * factorial(4) -> 5 * 4 * factorial(3) -> ... -> 5 * 4 * 3 * 2 * 1

4.2 다중 재귀 호출 – 피보나치 수열

// 비효율적인 순수 재귀 구현 - O(2^n)
function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(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 배열 재귀 - 배열 합계

// 배열을 재귀적으로 처리
function arraySum(arr, index = 0) {
  // 베이스 케이스: 배열 끝에 도달
  if (index >= arr.length) return 0;
  
  // 현재 요소 + 나머지 배열의 합
  return arr[index] + arraySum(arr, index + 1);
}

console.log(arraySum([1, 2, 3, 4, 5])); // 15

4.4 트리 구조 재귀 - 이진 트리 순회

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

// 전위 순회 (Pre-order)
function preOrder(node, result = []) {
  if (!node) return result;
  
  result.push(node.value);      // 현재 노드 방문
  preOrder(node.left, result);  // 왼쪽 서브트리
  preOrder(node.right, result); // 오른쪽 서브트리
  
  return result;
}

// 트리 깊이 계산
function maxDepth(node) {
  if (!node) return 0;
  
  const leftDepth = maxDepth(node.left);
  const rightDepth = maxDepth(node.right);
  
  return Math.max(leftDepth, rightDepth) + 1;
}

4.5 백트래킹 - 순열 생성

// 모든 순열을 재귀적으로 생성
function permutations(arr) {
  const result = [];
  
  function backtrack(current, remaining) {
    // 베이스 케이스: 모든 요소를 사용함
    if (remaining.length === 0) {
      result.push([...current]);
      return;
    }
    
    // 각 요소를 선택하여 재귀 호출
    for (let i = 0; i < remaining.length; i++) {
      current.push(remaining[i]);
      const next = [...remaining.slice(0, i), ...remaining.slice(i + 1)];
      backtrack(current, next);
      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 꼬리 재귀 최적화

// 일반 재귀
function factorialNormal(n) {
  if (n <= 1) return 1;
  return n * factorialNormal(n - 1);
}

// 꼬리 재귀 형태로 변환
function factorialTail(n, acc = 1) {
  if (n <= 1) return acc;
  return factorialTail(n - 1, n * acc); // 마지막 작업이 재귀 호출
}

5.3 반복문으로 전환

스택 오버플로우 위험이 있는 깊은 재귀는 반복문으로 구현하는 것이 안전합니다. 특히 선형 재귀는 쉽게 반복문으로 변환할 수 있습니다.

6. 실전 활용 예제

재귀 함수 마스터하기는 코딩 테스트와 실무에서 필수적입니다. DFS(깊이 우선 탐색)로 그래프를 탐색하거나, Quick Sort/Merge Sort로 정렬을 구현하고, 동적 프로그래밍 문제를 해결할 때 재귀가 핵심입니다. 파일 시스템 탐색, JSON 파싱, DOM 트리 순회 등 실무에서도 재귀는 트리/그래프 구조 처리에 광범위하게 사용됩니다. 재귀 함수 마스터하기를 통해 복잡한 문제를 우아하게 해결하는 능력을 키울 수 있습니다.

핵심 체크리스트

• ✅ 베이스 케이스를 명확히 정의했는가?
• ✅ 재귀 호출이 베이스 케이스로 수렴하는가?
• ✅ 스택 오버플로우 위험은 없는가?
• ✅ 중복 계산을 최적화했는가?
• ✅ 시간/공간 복잡도를 분석했는가?

재귀 함수 마스터하기는 연습을 통해 완성됩니다. 간단한 문제부터 시작해 점진적으로 복잡한 재귀 패턴을 익혀나가세요!