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

재귀 함수 마스터하기: 알고리즘의 핵심 개념 완전 정복

재귀 함수 마스터하기는 모든 개발자가 반드시 익혀야 할 필수 알고리즘 개념입니다. 재귀(Recursion)는 함수가 자기 자신을 호출하는 프로그래밍 기법으로, 복잡한 문제를 작은 하위 문제로 분할하여 해결하는 분할 정복(Divide and Conquer) 전략의 핵심입니다. 트리 탐색, 백트래킹, 동적 프로그래밍 등 다양한 알고리즘의 기초가 되며, 코딩 테스트에서도 빈번하게 출제됩니다. 재귀 함수는 기본 케이스(Base Case)와 재귀 케이스(Recursive Case)로 구성되며, 올바른 종료 조건 설정이 무한 루프를 방지하는 핵심입니다.

재귀 함수의 동작 원리 상세 설명

재귀 함수는 콜 스택(Call Stack) 메커니즘을 기반으로 동작합니다. 함수가 호출될 때마다 현재 실행 컨텍스트가 스택에 저장되고, 기본 케이스에 도달하면 스택에서 역순으로 함수가 반환되며 결과를 계산합니다. 예를 들어 팩토리얼 계산 시 factorial(5)는 5 * factorial(4)를 호출하고, 이는 다시 4 * factorial(3)을 호출하는 방식으로 진행됩니다. factorial(0) 또는 factorial(1)에서 1을 반환하는 기본 케이스에 도달하면, 스택에 쌓인 함수들이 차례로 반환되며 5 * 4 * 3 * 2 * 1 = 120이라는 최종 결과를 계산합니다. 이러한 후입선출(LIFO) 구조는 재귀의 핵심이며, 각 호출은 독립적인 지역 변수와 매개변수를 가집니다. 재귀 함수 설계 시 반드시 종료 조건(기본 케이스)을 명확히 정의하고, 각 재귀 호출이 문제를 점진적으로 작게 만들어 종료 조건으로 수렴하도록 해야 합니다.

시간 및 공간 복잡도 분석

재귀 함수의 시간 복잡도는 재귀 호출의 총 횟수와 각 호출에서 수행되는 작업량에 따라 결정됩니다. 단순 선형 재귀(예: 팩토리얼)는 O(n) 시간 복잡도를 가지며, 피보나치 수열의 순수 재귀 구현은 중복 계산으로 인해 O(2^n)의 지수 시간 복잡도를 가집니다. 이진 탐색과 같은 분할 정복 재귀는 O(log n)의 효율적인 시간 복잡도를 보입니다. 공간 복잡도는 주로 콜 스택의 최대 깊이에 의해 결정되며, 재귀 깊이가 n이면 O(n)의 공간을 사용합니다. 이는 반복문 구현(O(1) 공간)과 비교했을 때 메모리 효율성이 낮을 수 있습니다. 깊은 재귀는 스택 오버플로우(Stack Overflow) 위험이 있으며, 대부분의 언어에서 스택 크기 제한(JavaScript는 약 10,000~50,000 호출)이 존재합니다. 따라서 재귀 깊이가 매우 깊어질 수 있는 경우 반복문이나 꼬리 재귀 최적화를 고려해야 합니다.

단계별 구현 과정

1단계: 기본 재귀 – 팩토리얼

가장 간단한 재귀 예제로 팩토리얼을 구현합니다. 기본 케이스와 재귀 케이스를 명확히 구분합니다.

function factorial(n) {
  // 기본 케이스: 재귀 종료 조건
  if (n === 0 || n === 1) {
    return 1;
  }
  // 재귀 케이스: 자기 자신을 호출
  return n * factorial(n - 1);
}

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

2단계: 배열 재귀 – 배열 합계

배열을 재귀적으로 처리하는 방법을 학습합니다. 배열을 점진적으로 줄여가며 문제를 해결합니다.

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

3단계: 다중 재귀 – 피보나치 수열

하나의 함수에서 여러 번 자신을 호출하는 다중 재귀를 구현합니다.

function fibonacci(n) {
  // 기본 케이스
  if (n <= 1) {
    return n;
  }
  // 다중 재귀: 두 번의 재귀 호출
  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(7)); // 13

4단계: 트리 재귀 - 깊이 우선 탐색

재귀는 트리 구조 탐색에 매우 적합합니다. DOM 트리나 파일 시스템 탐색에 활용됩니다.

function dfs(node) {
  if (!node) return;
  
  // 현재 노드 처리
  console.log(node.value);
  
  // 자식 노드들을 재귀적으로 탐색
  if (node.children) {
    node.children.forEach(child => dfs(child));
  }
}

const tree = {
  value: 1,
  children: [
    { value: 2, children: [{ value: 4 }, { value: 5 }] },
    { value: 3, children: [{ value: 6 }] }
  ]
};

dfs(tree); // 1, 2, 4, 5, 3, 6

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 newRemaining = remaining.filter((_, idx) => idx !== i);
      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]]

최적화 방법

메모이제이션(Memoization): 중복 계산을 방지하기 위해 이전 결과를 캐싱합니다. 피보나치 수열을 O(2^n)에서 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)); // 빠르게 계산

꼬리 재귀 최적화(Tail Call Optimization): 재귀 호출이 함수의 마지막 연산일 때 스택을 재사용하여 공간 복잡도를 O(1)로 줄입니다.

function factorialTail(n, acc = 1) {
  if (n <= 1) return acc;
  return factorialTail(n - 1, n * acc);
}

반복문 변환: 스택 오버플로우 위험이 있는 경우 반복문으로 변환합니다. 대부분의 재귀는 스택 자료구조를 사용해 반복문으로 구현 가능합니다.

실전 활용 예제

재귀 함수 마스터하기는 실전 코딩 테스트에서 필수적입니다. LeetCode, 프로그래머스 등에서 트리 순회(이진 트리 최대 깊이, 경로 합), 백트래킹(N-Queen, 조합), 분할 정복(병합 정렬, 퀵 정렬), 동적 프로그래밍(최장 공통 부분 수열) 등 다양한 문제에 재귀가 활용됩니다. 실무에서는 파일 시스템 탐색, JSON 객체 깊은 복사, React 컴포넌트 트리 렌더링 등에 사용됩니다. 재귀 함수 마스터하기를 통해 복잡한 문제를 우아하게 해결하는 능력을 키울 수 있습니다.