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

1. 알고리즘 소개 및 개념

재귀 함수 마스터하기는 프로그래밍에서 가장 중요한 개념 중 하나입니다. 재귀(Recursion)란 함수가 자기 자신을 호출하는 프로그래밍 기법으로, 복잡한 문제를 더 작은 동일한 형태의 부분 문제로 나누어 해결합니다. 재귀 함수는 기본 케이스(Base Case)와 재귀 케이스(Recursive Case)로 구성되며, 기본 케이스는 재귀 호출을 멈추는 조건이고, 재귀 케이스는 문제를 더 작은 문제로 분할하여 자신을 다시 호출하는 부분입니다. 트리 순회, 팩토리얼 계산, 피보나치 수열, 분할 정복 알고리즘 등 다양한 분야에서 활용되며, 코딩 테스트에서도 자주 출제되는 핵심 알고리즘입니다.

2. 동작 원리 상세 설명

재귀 함수의 동작 원리는 콜 스택(Call Stack)을 기반으로 합니다. 함수가 호출될 때마다 현재 실행 상태가 스택에 저장되고, 새로운 함수 호출이 스택 위에 쌓입니다. 재귀 함수가 실행되면 먼저 기본 케이스를 확인합니다. 기본 케이스에 도달하지 않았다면, 문제를 더 작은 단위로 분할하여 자신을 다시 호출합니다. 이 과정이 반복되어 스택에 여러 함수 호출이 쌓이게 됩니다. 기본 케이스에 도달하면 더 이상 재귀 호출을 하지 않고 값을 반환하기 시작합니다. 반환된 값들은 스택에서 하나씩 제거되면서(LIFO 방식) 이전 호출로 돌아가고, 각 단계에서 계산된 결과가 조합되어 최종 결과를 생성합니다. 예를 들어, factorial(3)을 호출하면 factorial(3) → factorial(2) → factorial(1) → factorial(0) 순서로 호출되고, 기본 케이스인 factorial(0)이 1을 반환하면 역순으로 1 → 1 → 2 → 6이 계산됩니다. 이러한 방식으로 재귀 함수는 복잡한 문제를 우아하게 해결할 수 있습니다.

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

재귀 함수의 시간 복잡도는 재귀 호출 횟수와 각 호출에서 수행되는 작업량에 따라 결정됩니다. 단순 재귀의 경우 팩토리얼은 O(n), 피보나치는 O(2^n)의 시간 복잡도를 가집니다. 피보나치의 경우 중복 계산이 발생하여 지수 시간이 소요되지만, 메모이제이션을 적용하면 O(n)으로 개선할 수 있습니다. 공간 복잡도는 재귀 호출 깊이에 비례하며, 콜 스택에 저장되는 함수 호출 정보의 최대 개수로 결정됩니다. 일반적으로 재귀 깊이가 n이면 O(n)의 공간 복잡도를 가집니다. 꼬리 재귀(Tail Recursion) 최적화가 지원되는 언어에서는 O(1)의 공간 복잡도로 개선할 수 있습니다. 분할 정복 알고리즘인 병합 정렬의 경우 시간 복잡도는 O(n log n), 공간 복잡도는 재귀 스택으로 인해 O(log n)입니다. 재귀를 사용할 때는 스택 오버플로우 위험성을 고려해야 하며, 재귀 깊이가 너무 깊어지면 반복문으로 전환하는 것이 좋습니다.

4. 단계별 구현 과정

4.1 기본 재귀 – 팩토리얼

팩토리얼은 재귀의 가장 기본적인 예제입니다. n! = n × (n-1) × … × 1의 수학적 정의를 그대로 코드로 표현합니다.

// 재귀를 사용한 팩토리얼
function factorial(n) {
  // 기본 케이스: 0! = 1
  if (n === 0 || n === 1) {
    return 1;
  }
  // 재귀 케이스: n! = n × (n-1)!
  return n * factorial(n - 1);
}

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

4.2 피보나치 수열 (기본 재귀)

피보나치 수열은 F(n) = F(n-1) + F(n-2)로 정의되며, 재귀로 구현하기 적합합니다.

// 기본 재귀 구현 (비효율적)
function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

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

4.3 배열 합계 구하기

배열의 모든 요소를 더하는 재귀 함수입니다. 배열을 점점 작게 만들어가며 문제를 해결합니다.

function sumArray(arr) {
  // 기본 케이스: 빈 배열
  if (arr.length === 0) return 0;
  
  // 재귀 케이스: 첫 요소 + 나머지 배열의 합
  return arr[0] + sumArray(arr.slice(1));
}

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

4.4 문자열 뒤집기

재귀를 사용하여 문자열을 역순으로 만듭니다.

function reverseString(str) {
  if (str === '') return '';
  return reverseString(str.substr(1)) + str[0];
}

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

4.5 이진 탐색 (재귀 버전)

정렬된 배열에서 특정 값을 O(log n) 시간에 찾는 분할 정복 알고리즘입니다.

function binarySearch(arr, target, left = 0, right = arr.length - 1) {
  // 기본 케이스: 찾지 못함
  if (left > right) return -1;
  
  const mid = Math.floor((left + right) / 2);
  
  // 찾은 경우
  if (arr[mid] === target) return mid;
  
  // 왼쪽 절반 탐색
  if (arr[mid] > target) {
    return binarySearch(arr, target, left, mid - 1);
  }
  
  // 오른쪽 절반 탐색
  return binarySearch(arr, target, mid + 1, right);
}

const sortedArr = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(binarySearch(sortedArr, 7)); // 3

4.6 트리 순회

재귀는 트리 구조를 탐색하는 데 가장 자연스러운 방법입니다.

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

// 전위 순회 (Pre-order)
function preOrder(node) {
  if (node === null) return;
  console.log(node.value);
  preOrder(node.left);
  preOrder(node.right);
}

// 중위 순회 (In-order)
function inOrder(node) {
  if (node === null) return;
  inOrder(node.left);
  console.log(node.value);
  inOrder(node.right);
}

// 후위 순회 (Post-order)
function postOrder(node) {
  if (node === null) return;
  postOrder(node.left);
  postOrder(node.right);
  console.log(node.value);
}

5. 최적화 방법

5.1 메모이제이션 (Memoization)

재귀 함수 마스터하기에서 가장 중요한 최적화 기법입니다. 이미 계산한 결과를 저장하여 중복 계산을 방지합니다.

// 메모이제이션을 적용한 피보나치
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)); // 빠르게 계산됨

5.2 꼬리 재귀 최적화

재귀 호출이 함수의 마지막 연산이 되도록 작성하여 스택 오버플로우를 방지합니다.

// 일반 재귀
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1); // 재귀 호출 후 곱셈 연산이 남음
}

// 꼬리 재귀
function factorialTail(n, acc = 1) {
  if (n <= 1) return acc;
  return factorialTail(n - 1, n * acc); // 재귀 호출이 마지막 연산
}

5.3 반복문으로 전환

재귀 깊이가 깊어질 경우 반복문으로 전환하는 것이 안전합니다.

// 반복문을 사용한 팩토리얼
function factorialIterative(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

6. 실전 활용 예제

재귀 함수 마스터하기는 다양한 실전 문제에 적용됩니다. 순열과 조합 생성, 하노이의 탑, 미로 찾기(백트래킹), JSON 객체 깊은 복사, 디렉토리 트리 탐색, 퀵 정렬과 병합 정렬 같은 분할 정복 알고리즘, 동적 프로그래밍 문제 등이 대표적입니다. 코딩 테스트에서는 DFS(깊이 우선 탐색), 트리/그래프 문제, 백트래킹 문제에서 재귀가 필수적으로 사용됩니다. 재귀 함수 마스터하기를 완벽히 이해하면 복잡한 알고리즘 문제를 우아하고 간결하게 해결할 수 있으며, 코드의 가독성과 유지보수성도 크게 향상됩니다.

실전 예제: 순열 생성

function permutation(arr, selectNum) {
  const result = [];
  if (selectNum === 1) return arr.map(v => [v]);
  
  arr.forEach((fixed, index, origin) => {
    const rest = [...origin.slice(0, index), ...origin.slice(index + 1)];
    const perms = permutation(rest, selectNum - 1);
    const attached = perms.map(perm => [fixed, ...perm]);
    result.push(...attached);
  });
  
  return result;
}

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