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

1. 알고리즘 소개 및 개념

재귀 함수 마스터하기는 프로그래밍에서 가장 중요한 개념 중 하나입니다. 재귀(Recursion)란 함수가 자기 자신을 호출하는 프로그래밍 기법으로, 복잡한 문제를 더 작은 하위 문제로 분할하여 해결하는 방식입니다. 재귀 함수는 반복문으로 해결하기 어려운 트리 구조 탐색, 분할 정복 알고리즘, 백트래킹 등에서 필수적으로 사용됩니다. 모든 재귀 함수는 기저 조건(Base Case)과 재귀 조건(Recursive Case)으로 구성되며, 기저 조건이 없으면 무한 루프에 빠지게 됩니다. 재귀적 사고는 알고리즘 문제 해결 능력을 한 단계 끌어올리는 핵심 스킬입니다.

2. 동작 원리 상세 설명

재귀 함수의 동작 원리는 콜 스택(Call Stack)을 기반으로 합니다. 함수가 호출될 때마다 현재 실행 컨텍스트가 스택에 쌓이고, 함수가 종료되면 스택에서 제거됩니다. 재귀 함수가 실행되면 먼저 기저 조건을 검사합니다. 기저 조건에 도달하지 않았다면 함수는 자기 자신을 다시 호출하며, 이때 문제의 크기는 점점 작아집니다. 예를 들어 팩토리얼 계산 시 factorial(5)는 5 * factorial(4)를 호출하고, factorial(4)는 4 * factorial(3)을 호출하는 식으로 진행됩니다. 기저 조건인 factorial(1) 또는 factorial(0)에 도달하면 재귀 호출이 멈추고, 스택에 쌓인 함수들이 역순으로 계산되어 최종 결과를 반환합니다. 이러한 과정에서 각 함수 호출은 독립적인 지역 변수와 매개변수를 가지며, 메모리 스택에 저장됩니다. 재귀의 핵심은 큰 문제를 작은 문제로 분해하고, 작은 문제의 해를 조합하여 큰 문제를 해결하는 것입니다.

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

재귀 함수의 시간 복잡도는 재귀 호출의 총 횟수와 각 호출에서 수행되는 작업량에 따라 결정됩니다. 단순 재귀의 경우 O(n)이지만, 피보나치 수열처럼 중복 계산이 발생하면 O(2^n)까지 증가할 수 있습니다. 공간 복잡도는 콜 스택의 최대 깊이에 비례하며, 일반적으로 O(n)입니다. 예를 들어 팩토리얼 함수는 n번 재귀 호출하므로 시간 복잡도 O(n), 공간 복잡도 O(n)을 가집니다. 반면 최적화되지 않은 피보나치는 시간 O(2^n), 공간 O(n)으로 매우 비효율적입니다. 이진 탐색의 재귀 버전은 시간 O(log n), 공간 O(log n)으로 효율적입니다. 꼬리 재귀 최적화(Tail Recursion Optimization)를 사용하면 일부 언어에서 공간 복잡도를 O(1)로 줄일 수 있습니다. 복잡도 분석 시 재귀 트리를 그려보면 호출 구조를 시각적으로 이해할 수 있습니다.

4. 단계별 구현 과정

Step 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

Step 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(7)); // 13
// 문제: fibonacci(7) 계산 시 fibonacci(5)가 2번, fibonacci(3)이 5번 계산됨

Step 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

Step 4: 이진 탐색 (재귀 버전)

분할 정복을 활용한 효율적인 재귀 예제입니다.

// 정렬된 배열에서 특정 값 찾기
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 sortedArr = [1, 3, 5, 7, 9, 11, 13];
console.log(binarySearch(sortedArr, 7)); // 3
console.log(binarySearch(sortedArr, 4)); // -1

Step 5: 트리 구조 탐색

재귀가 가장 빛나는 영역인 트리 탐색입니다.

// 이진 트리 노드 구조
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// 이진 트리의 모든 노드 값 합계
function sumTree(root) {
  // 기저 조건: 노드가 null
  if (root === null) {
    return 0;
  }
  
  // 재귀 조건: 현재 노드 + 왼쪽 서브트리 + 오른쪽 서브트리
  return root.value + sumTree(root.left) + sumTree(root.right);
}

// 트리 생성 및 테스트
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(sumTree(root)); // 15

5. 최적화 방법

메모이제이션(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 (빠르게 계산됨)

// 꼬리 재귀 최적화 예제
function factorialTail(n, accumulator = 1) {
  if (n <= 1) {
    return accumulator;
  }
  // 마지막 연산이 재귀 호출 자체
  return factorialTail(n - 1, n * accumulator);
}

또한 재귀를 반복문으로 변환하거나, 스택 자료구조를 명시적으로 사용하는 방법도 있습니다. 재귀 깊이 제한을 고려하여 큰 입력에는 반복문 사용을 권장합니다.

6. 실전 활용 예제

재귀 함수 마스터하기를 통해 실전에서 자주 등장하는 문제들을 해결할 수 있습니다. 대표적인 활용 사례로는 DFS(깊이 우선 탐색)를 이용한 그래프 탐색, 퀵소트/병합정렬 같은 분할 정복 알고리즘, N-Queen 문제나 미로 찾기 같은 백트래킹, 하노이의 탑, 조합/순열 생성, JSON 객체 깊은 복사, 파일 시스템 탐색 등이 있습니다. 코딩 테스트에서는 트리/그래프 문제의 90% 이상이 재귀로 해결되며, 동적 프로그래밍의 Top-down 방식도 재귀를 기반으로 합니다. 재귀적 사고방식을 익히면 복잡한 문제를 우아하고 간결하게 해결할 수 있습니다.

마무리

재귀 함수는 처음에는 어렵게 느껴질 수 있지만, 기저 조건과 재귀 조건을 명확히 정의하는 연습을 통해 자연스럽게 익힐 수 있습니다. 단순한 문제부터 시작하여 점진적으로 복잡한 문제로 나아가며, 항상 콜 스택과 실행 흐름을 머릿속으로 그려보는 습관을 들이세요. 재귀 함수 마스터하기를 통해 알고리즘 실력을 한 단계 끌어올리시기 바랍니다.