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

1. 알고리즘 소개 및 개념

재귀 함수 마스터하기는 프로그래밍에서 가장 중요한 개념 중 하나입니다. 재귀 함수(Recursive Function)란 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법입니다. 복잡한 문제를 더 작은 하위 문제로 분할하여 해결하는 분할 정복(Divide and Conquer) 전략의 핵심이며, 트리 순회, 그래프 탐색, 동적 프로그래밍 등 다양한 알고리즘의 기초가 됩니다. 재귀 함수는 기저 조건(Base Case)과 재귀 조건(Recursive Case)으로 구성되며, 기저 조건이 없으면 무한 루프에 빠지게 됩니다. 효과적인 재귀 함수 설계는 코드의 간결성과 가독성을 높이며, 복잡한 알고리즘 문제를 우아하게 해결할 수 있게 해줍니다.

2. 동작 원리 상세 설명

재귀 함수의 동작 원리는 콜 스택(Call Stack)을 기반으로 합니다. 함수가 호출될 때마다 현재 실행 컨텍스트가 스택에 푸시되고, 함수가 반환될 때 팝됩니다. 예를 들어 factorial(5)를 호출하면, factorial(5) → factorial(4) → factorial(3) → factorial(2) → factorial(1) 순서로 스택에 쌓입니다. 기저 조건에 도달하면(예: n=1), 스택이 역순으로 풀리면서 각 단계의 결과를 계산합니다: 1 → 2×1 → 3×2 → 4×6 → 5×24 = 120. 이러한 과정을 ‘와인딩(winding)’과 ‘언와인딩(unwinding)’이라고 합니다. 재귀 함수는 문제를 더 작은 부분 문제로 나누고, 각 부분 문제의 해를 결합하여 원래 문제를 해결합니다. 중요한 점은 각 재귀 호출이 원래 문제보다 작은 문제를 다루어야 하며, 최종적으로 기저 조건에 도달해야 한다는 것입니다. 이를 통해 유한한 시간 내에 문제가 해결됩니다.

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

재귀 함수의 시간 복잡도는 재귀 호출의 총 횟수와 각 호출에서 수행되는 작업량에 의해 결정됩니다. 단순 재귀(예: 팩토리얼)는 O(n)의 시간 복잡도를 가지며, 피보나치 수열의 순수 재귀 구현은 O(2^n)으로 매우 비효율적입니다. 공간 복잡도는 주로 콜 스택의 최대 깊이에 의해 결정되며, 대부분 O(n)입니다. 예를 들어, factorial(n)은 n번의 재귀 호출로 O(n) 공간을 사용합니다. 이진 트리 순회는 최악의 경우 O(h) 공간을 사용하며, 여기서 h는 트리의 높이입니다. 메모이제이션을 사용하면 시간 복잡도를 크게 개선할 수 있습니다. 예를 들어, 피보나치 수열을 메모이제이션으로 구현하면 O(2^n)에서 O(n)으로 개선됩니다. 꼬리 재귀 최적화(Tail Call Optimization)를 지원하는 언어에서는 공간 복잡도를 O(1)로 줄일 수 있습니다.

4. 단계별 구현 과정

4.1 기본 재귀 – 팩토리얼

// 가장 기본적인 재귀 함수 예제
function factorial(n) {
  // 기저 조건: 재귀를 멈추는 조건
  if (n <= 1) {
    return 1;
  }
  
  // 재귀 조건: 자기 자신을 호출
  return n * factorial(n - 1);
}

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

4.2 피보나치 수열 - 기본 재귀

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

console.log(fibonacci(6)); // 8
// 문제점: fibonacci(10) 이상부터 느려짐

4.3 메모이제이션을 활용한 최적화

// 메모이제이션으로 O(n)으로 개선
function fibonacciMemo(n, memo = {}) {
  // 이미 계산된 값이 있으면 반환
  if (n in memo) {
    return memo[n];
  }
  
  if (n <= 1) {
    return n;
  }
  
  // 계산 결과를 저장
  memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
  return memo[n];
}

console.log(fibonacciMemo(50)); // 12586269025 (빠르게 계산)

4.4 배열 재귀 - 배열 합 구하기

// 배열의 모든 요소 합 구하기
function arraySum(arr) {
  // 기저 조건: 빈 배열
  if (arr.length === 0) {
    return 0;
  }
  
  // 첫 번째 요소 + 나머지 배열의 합
  return arr[0] + arraySum(arr.slice(1));
}

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

4.5 문자열 재귀 - 문자열 뒤집기

// 재귀로 문자열 뒤집기
function reverseString(str) {
  if (str === '') {
    return '';
  }
  return reverseString(str.substr(1)) + str.charAt(0);
}

console.log(reverseString('hello')); // 'olleh'

4.6 깊은 객체 탐색

// 중첩된 객체에서 값 찾기
function findValue(obj, key) {
  // 현재 레벨에서 키를 찾으면 반환
  if (key in obj) {
    return obj[key];
  }
  
  // 모든 속성을 순회하며 재귀 탐색
  for (let k in obj) {
    if (typeof obj[k] === 'object' && obj[k] !== null) {
      const result = findValue(obj[k], key);
      if (result !== undefined) {
        return result;
      }
    }
  }
  
  return undefined;
}

const data = {
  user: {
    profile: {
      name: 'John',
      settings: {
        theme: 'dark'
      }
    }
  }
};

console.log(findValue(data, 'theme')); // 'dark'

5. 최적화 방법

재귀 함수 마스터하기를 위해서는 최적화 기법을 반드시 알아야 합니다. 첫째, 메모이제이션(Memoization)을 사용하여 중복 계산을 제거합니다. 이미 계산된 값을 객체나 Map에 저장하여 재사용하면 지수 시간 복잡도를 선형으로 줄일 수 있습니다. 둘째, 꼬리 재귀(Tail Recursion)로 변환하면 일부 컴파일러에서 스택 오버플로우를 방지할 수 있습니다. 꼬리 재귀는 재귀 호출이 함수의 마지막 작업인 경우를 말합니다. 셋째, 가능한 경우 반복문으로 변환하는 것도 고려해야 합니다. 반복문은 스택 오버플로우 위험이 없고 일반적으로 더 빠릅니다. 넷째, 재귀 깊이를 제한하여 스택 오버플로우를 방지합니다. 다섯째, 동적 프로그래밍으로 전환하여 상향식(Bottom-up) 접근법을 사용하면 메모리 효율성을 높일 수 있습니다.

꼬리 재귀 최적화 예제

// 일반 재귀 (스택 오버플로우 위험)
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

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

console.log(factorialTail(5)); // 120

6. 실전 활용 예제

재귀 함수는 트리/그래프 순회(DFS, BFS), 백트래킹(N-Queens, 미로 찾기), 분할 정복(퀵 정렬, 병합 정렬, 이진 탐색), 조합/순열 생성, 하노이 탑 문제, JSON 파싱, 파일 시스템 탐색, 프랙탈 그리기 등 다양한 실전 문제에 활용됩니다. 코딩 테스트에서는 트리 구조 문제, 깊이 우선 탐색, 동적 프로그래밍 문제에서 자주 등장합니다.

이진 트리 순회 예제

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

// 전위 순회 (Pre-order)
function preorderTraversal(root, result = []) {
  if (root === null) {
    return result;
  }
  
  result.push(root.value);
  preorderTraversal(root.left, result);
  preorderTraversal(root.right, result);
  
  return result;
}

// 트리 깊이 구하기
function maxDepth(root) {
  if (root === null) {
    return 0;
  }
  
  const leftDepth = maxDepth(root.left);
  const rightDepth = maxDepth(root.right);
  
  return Math.max(leftDepth, rightDepth) + 1;
}

// 사용 예제
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

console.log(preorderTraversal(root)); // [1, 2, 4, 5, 3]
console.log(maxDepth(root)); // 3

순열 생성 예제

// 배열의 모든 순열 생성
function permutations(arr) {
  if (arr.length <= 1) {
    return [arr];
  }
  
  const result = [];
  
  for (let i = 0; i < arr.length; i++) {
    const current = arr[i];
    const remaining = arr.slice(0, i).concat(arr.slice(i + 1));
    const remainingPerms = permutations(remaining);
    
    for (let perm of remainingPerms) {
      result.push([current, ...perm]);
    }
  }
  
  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]]

재귀 함수 마스터하기를 통해 복잡한 알고리즘 문제를 우아하고 효율적으로 해결할 수 있습니다. 기저 조건 설정, 메모이제이션, 꼬리 재귀 최적화 등의 기법을 익히면 코딩 테스트와 실무에서 강력한 무기가 됩니다.