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

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) 순서로 스택에 쌓이고, factorial(1)이 1을 반환하면서 역순으로 계산되어 최종 결과 120이 반환됩니다. 이러한 과정에서 각 재귀 호출은 메모리 스택 공간을 차지하므로, 깊이가 깊어질수록 스택 오버플로우 위험이 증가합니다.

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

재귀 함수의 복잡도는 문제의 특성에 따라 크게 달라집니다. 시간 복잡도는 재귀 호출 횟수와 각 호출에서 수행되는 작업량에 의해 결정됩니다. 선형 재귀(예: 팩토리얼)는 O(n), 이진 재귀(예: 피보나치)는 O(2^n), 분할 정복(예: 병합 정렬)은 O(n log n)의 시간 복잡도를 가집니다.

공간 복잡도는 최대 재귀 깊이에 비례합니다. 각 재귀 호출은 스택 프레임을 생성하므로, 최대 깊이가 n이면 O(n)의 공간이 필요합니다. 피보나치 수열의 순수 재귀 구현은 O(2^n) 시간 복잡도와 O(n) 공간 복잡도를 가지지만, 메모이제이션을 적용하면 O(n) 시간, O(n) 공간으로 최적화할 수 있습니다. 꼬리 재귀 최적화를 지원하는 언어에서는 공간 복잡도를 O(1)로 줄일 수 있습니다.

4. 단계별 구현 과정

4.1 기본 재귀 함수 – 팩토리얼

// 팩토리얼: n! = n × (n-1) × ... × 1
function factorial(n) {
  // 기저 조건: 0! = 1, 1! = 1
  if (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
console.log(fibonacci(10)); // 55

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 문자열 뒤집기

// 문자열을 재귀로 뒤집기
function reverseString(str) {
  // 기저 조건: 빈 문자열이거나 한 글자
  if (str.length <= 1) {
    return str;
  }
  
  // 재귀 조건: 마지막 문자 + 나머지 뒤집기
  return str[str.length - 1] + reverseString(str.slice(0, -1));
}

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

4.5 이진 탐색 - 분할 정복

// 정렬된 배열에서 이진 탐색
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);
  } else {
    return binarySearch(arr, target, mid + 1, right);
  }
}

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

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)); // 12586269025

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

// 팩토리얼 - 꼬리 재귀 버전
function factorialTail(n, accumulator = 1) {
  if (n <= 1) {
    return accumulator;
  }
  
  // 마지막 연산이 재귀 호출만 있음
  return factorialTail(n - 1, n * accumulator);
}

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

재귀 함수 마스터하기의 핵심은 적절한 최적화 기법을 선택하는 것입니다. 메모이제이션은 중복 계산을 제거하여 지수 시간을 선형 시간으로 줄일 수 있으며, 꼬리 재귀는 일부 컴파일러에서 반복문으로 자동 변환되어 스택 오버플로우를 방지합니다.

6. 실전 활용 예제

6.1 순열 생성

// 배열의 모든 순열 생성
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 (const 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]]

6.2 트리 순회

// 이진 트리 깊이 우선 탐색
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function inorderTraversal(node, result = []) {
  if (node === null) {
    return result;
  }
  
  inorderTraversal(node.left, result);
  result.push(node.value);
  inorderTraversal(node.right, result);
  
  return result;
}

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
console.log(inorderTraversal(root)); // [2, 1, 3]

재귀 함수 마스터하기를 통해 트리 구조, 그래프 탐색, 백트래킹 문제를 효율적으로 해결할 수 있습니다. 순열, 조합, 부분집합 생성과 같은 조합론 문제나 N-Queen, 미로 찾기 같은 백트래킹 문제에서 재귀는 필수적인 도구입니다.

재귀 함수 사용 시 주의사항

• 기저 조건 필수: 반드시 종료 조건을 명확히 정의해야 합니다.
• 스택 오버플로우 방지: 재귀 깊이가 너무 깊으면 스택 오버플로우가 발생할 수 있습니다.
• 성능 고려: 순수 재귀는 비효율적일 수 있으므로 메모이제이션이나 동적 프로그래밍을 고려하세요.
• 디버깅 어려움: 재귀 호출 스택을 추적하기 어려우므로 작은 입력으로 테스트하세요.

재귀 함수 마스터하기는 시간이 걸리지만, 한번 익히면 복잡한 알고리즘 문제를 우아하게 해결할 수 있는 강력한 무기가 됩니다. 기본 개념부터 시작해서 다양한 예제를 직접 구현해보며 재귀적 사고방식을 체득하는 것이 중요합니다.