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

1. 알고리즘 소개 및 개념

재귀 함수 마스터하기는 프로그래밍에서 가장 중요한 개념 중 하나입니다. 재귀(Recursion)는 함수가 자기 자신을 호출하는 프로그래밍 기법으로, 복잡한 문제를 더 작은 하위 문제로 분할하여 해결하는 강력한 도구입니다. 재귀 함수는 기저 조건(Base Case)과 재귀 조건(Recursive Case)으로 구성되며, 기저 조건은 재귀 호출을 종료시키는 역할을 합니다. 트리 순회, 백트래킹, 분할 정복 알고리즘 등 다양한 알고리즘 문제에서 재귀는 필수적인 해결 방법이며, 코딩 테스트에서도 자주 출제되는 중요한 주제입니다. 재귀적 사고방식을 익히면 복잡한 문제를 직관적이고 간결하게 해결할 수 있습니다.

2. 동작 원리 상세 설명

재귀 함수의 동작 원리는 콜 스택(Call Stack)을 기반으로 합니다. 함수가 호출될 때마다 현재 실행 컨텍스트가 스택에 쌓이고, 함수가 종료되면 스택에서 제거됩니다. 재귀 함수가 실행되면 기저 조건에 도달할 때까지 계속해서 자기 자신을 호출하며 스택에 쌓입니다. 기저 조건에 도달하면 더 이상 재귀 호출을 하지 않고, 스택에 쌓인 함수들이 역순으로 실행되면서 결과를 반환합니다.

예를 들어 팩토리얼 계산 factorial(3)을 실행하면, factorial(3) → factorial(2) → factorial(1) → factorial(0) 순서로 호출되고, factorial(0)이 1을 반환하면 역순으로 1 → 1 → 2 → 6이 계산되어 최종 결과가 반환됩니다. 이러한 과정을 ‘되감기(Unwinding)’라고 하며, 재귀의 핵심 메커니즘입니다. 각 재귀 호출은 독립적인 지역 변수와 매개변수를 가지므로, 호출 단계마다 고유한 상태를 유지할 수 있습니다.

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

재귀 함수의 시간 복잡도는 재귀 호출 횟수와 각 호출에서 수행되는 작업량에 따라 결정됩니다. 단순 재귀(예: 팩토리얼)는 O(n)의 시간 복잡도를 가지며, 이진 재귀(예: 피보나치)는 O(2^n)으로 지수적으로 증가할 수 있습니다. 분할 정복 알고리즘(예: 병합 정렬)은 O(n log n)의 효율적인 시간 복잡도를 보입니다.

공간 복잡도는 주로 콜 스택의 깊이에 의해 결정됩니다. 재귀 깊이가 n이면 O(n)의 공간 복잡도를 가지며, 이는 스택 오버플로우의 원인이 될 수 있습니다. 꼬리 재귀 최적화(Tail Call Optimization)가 지원되는 언어에서는 O(1)의 공간 복잡도로 개선할 수 있습니다. 메모이제이션을 사용하면 추가 메모리를 사용하여 시간 복잡도를 크게 개선할 수 있으며, 이는 동적 프로그래밍의 기초가 됩니다.

4. 단계별 구현 과정

4.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 피보나치 수열 – 기본 재귀

이진 재귀의 대표적인 예제입니다. 하지만 비효율적이므로 최적화가 필요합니다.

function fibonacci(n) {
  // 기저 조건
  if (n <= 1) {
    return n;
  }
  
  // 재귀 조건: F(n) = F(n-1) + F(n-2)
  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(6)); // 8
// 주의: 큰 n에 대해서는 매우 느립니다

4.3 배열 합계 구하기

배열을 재귀적으로 처리하는 방법을 보여줍니다.

function sumArray(arr, index = 0) {
  // 기저 조건: 배열의 끝에 도달
  if (index >= arr.length) {
    return 0;
  }
  
  // 재귀 조건: 현재 요소 + 나머지 배열의 합
  return arr[index] + sumArray(arr, index + 1);
}

console.log(sumArray([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 deepClone(obj) {
  // 기저 조건: 객체가 아닌 경우
  if (obj === null || typeof obj !== 'object') {
    return obj;
  }
  
  // 배열 처리
  if (Array.isArray(obj)) {
    return obj.map(item => deepClone(item));
  }
  
  // 객체 처리
  const cloned = {};
  for (let key in obj) {
    if (obj.hasOwnProperty(key)) {
      cloned[key] = deepClone(obj[key]);
    }
  }
  
  return cloned;
}

const original = { a: 1, b: { c: 2, d: [3, 4] } };
const copy = deepClone(original);
console.log(copy); // { a: 1, b: { c: 2, d: [3, 4] } }

5. 최적화 방법

5.1 메모이제이션

계산 결과를 캐싱하여 중복 계산을 방지합니다.

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 factorialTail(n, accumulator = 1) {
  if (n <= 1) {
    return accumulator;
  }
  
  // 꼬리 재귀: 재귀 호출이 마지막 작업
  return factorialTail(n - 1, n * accumulator);
}

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

6. 실전 활용 예제

재귀 함수 마스터하기를 통해 다양한 실전 문제를 해결할 수 있습니다. 트리 구조 탐색(DFS), 백트래킹을 이용한 순열/조합 생성, 분할 정복 알고리즘(퀵소트, 병합정렬), 동적 프로그래밍 문제 등이 대표적입니다. 파일 시스템 탐색, JSON 파싱, DOM 트리 순회 등 실무에서도 재귀는 자주 사용됩니다. 재귀를 마스터하면 복잡한 문제를 간결하고 우아하게 해결할 수 있으며, 알고리즘적 사고력을 크게 향상시킬 수 있습니다.