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

1. 알고리즘 소개 및 개념

재귀 함수 마스터하기는 프로그래밍에서 가장 중요한 개념 중 하나입니다. 재귀 함수(Recursive Function)란 함수가 자기 자신을 호출하는 프로그래밍 기법으로, 복잡한 문제를 더 작은 하위 문제로 분할하여 해결하는 분할 정복(Divide and Conquer) 방식의 핵심입니다. 재귀는 트리 순회, 백트래킹, 동적 프로그래밍 등 다양한 알고리즘의 기초가 되며, 코딩 테스트에서 자주 출제되는 필수 개념입니다. 재귀 함수는 반드시 종료 조건(Base Case)과 재귀 호출(Recursive Case)로 구성되어야 하며, 이 두 요소가 올바르게 설계되지 않으면 무한 루프에 빠지거나 스택 오버플로우가 발생할 수 있습니다.

2. 동작 원리 상세 설명

재귀 함수의 동작 원리는 콜 스택(Call Stack)을 이해하는 것이 핵심입니다. 함수가 호출될 때마다 해당 함수의 실행 컨텍스트가 스택에 쌓이고, 함수가 종료되면 스택에서 제거됩니다. 재귀 함수는 자기 자신을 반복적으로 호출하면서 스택에 여러 층의 실행 컨텍스트를 쌓아가다가, 종료 조건에 도달하면 역순으로 스택을 해제하며 결과를 반환합니다.

예를 들어, 팩토리얼 계산 factorial(5)를 실행하면 다음과 같은 과정을 거칩니다:

• factorial(5) 호출 → 5 * factorial(4) 대기
• factorial(4) 호출 → 4 * factorial(3) 대기
• factorial(3) 호출 → 3 * factorial(2) 대기
• factorial(2) 호출 → 2 * factorial(1) 대기
• factorial(1) 호출 → 종료 조건 도달, 1 반환
• 역순으로 계산: 2*1=2 → 3*2=6 → 4*6=24 → 5*24=120

이처럼 재귀는 문제를 점진적으로 축소하면서 해결하며, 각 단계의 결과를 조합하여 최종 답을 도출합니다. 재귀 함수를 설계할 때는 항상 “어떤 조건에서 재귀를 멈출 것인가”와 “어떻게 문제를 더 작게 만들 것인가”를 고민해야 합니다.

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

재귀 함수의 복잡도는 문제의 성격에 따라 크게 달라집니다. 시간 복잡도는 재귀 호출이 몇 번 발생하는지, 각 호출에서 얼마나 많은 작업을 수행하는지에 따라 결정됩니다.

대표적인 시간 복잡도 패턴:

• 선형 재귀 (Linear Recursion): 팩토리얼, 배열 합계 등 – O(n)
• 이진 재귀 (Binary Recursion): 피보나치(단순 구현) – O(2^n)
• 분할 정복 재귀: 병합 정렬, 퀵 정렬 – O(n log n)
• 다중 분기 재귀: 하노이의 탑 – O(2^n)

공간 복잡도: 재귀 함수의 공간 복잡도는 주로 콜 스택의 깊이에 의해 결정됩니다. 최대 재귀 깊이가 n이라면 공간 복잡도는 O(n)입니다. 예를 들어, factorial(n)은 n번의 재귀 호출이 발생하므로 O(n)의 스택 공간을 사용합니다. 이는 반복문으로 구현할 때의 O(1) 공간 복잡도보다 비효율적일 수 있으며, 입력이 클 경우 스택 오버플로우의 위험이 있습니다. 따라서 꼬리 재귀 최적화(Tail Recursion Optimization)나 메모이제이션(Memoization) 기법을 활용하여 효율성을 개선할 필요가 있습니다.

4. 단계별 구현 과정

4.1 기본 재귀 – 팩토리얼

가장 간단한 재귀 예제부터 시작하겠습니다:

// 팩토리얼 계산
function factorial(n) {
  // 종료 조건 (Base Case)
  if (n === 0 || n === 1) {
    return 1;
  }
  
  // 재귀 호출 (Recursive Case)
  return n * factorial(n - 1);
}

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

4.2 피보나치 수열 – 기본 구현

피보나치 수열은 재귀의 대표적인 예제이지만, 단순 구현은 비효율적입니다:

// 비효율적인 피보나치 (O(2^n))
function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(10)); // 55
// fibonacci(40)은 매우 느림!

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 === '') return '';
  return reverseString(str.substr(1)) + str.charAt(0);
}

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

4.5 이진 탐색 (Binary Search)

분할 정복 방식의 재귀 활용:

// 재귀적 이진 탐색
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 sortedArray = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(binarySearch(sortedArray, 7)); // 3
console.log(binarySearch(sortedArray, 10)); // -1

4.6 깊이 우선 탐색 (DFS)

트리나 그래프 탐색에 재귀를 활용:

// 트리 구조
const tree = {
  value: 1,
  children: [
    {
      value: 2,
      children: [
        { value: 4, children: [] },
        { value: 5, children: [] }
      ]
    },
    {
      value: 3,
      children: [
        { value: 6, children: [] }
      ]
    }
  ]
};

// DFS로 트리 순회
function dfs(node, result = []) {
  if (!node) return result;
  
  result.push(node.value);
  
  for (const child of node.children) {
    dfs(child, result);
  }
  
  return result;
}

console.log(dfs(tree)); // [1, 2, 4, 5, 3, 6]

5. 최적화 방법

5.1 메모이제이션 (Memoization)

이미 계산한 결과를 저장하여 중복 계산을 방지합니다:

// 메모이제이션을 활용한 피보나치 (O(n))
function fibonacciMemo(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  
  memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
  return memo[n];
}

console.log(fibonacciMemo(40)); // 빠르게 계산됨!
console.log(fibonacciMemo(100)); // 354224848179262000000

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

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

// 꼬리 재귀 팩토리얼
function factorialTail(n, accumulator = 1) {
  if (n === 0 || n === 1) {
    return accumulator;
  }
  return factorialTail(n - 1, n * accumulator);
}

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

5.3 반복문 변환

재귀 깊이가 너무 깊어질 경우 반복문으로 변환하는 것도 좋은 방법입니다:

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

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

6. 실전 활용 예제

재귀 함수 마스터하기를 통해 다양한 실전 문제를 해결할 수 있습니다. 순열과 조합 생성: 백트래킹을 활용한 모든 경우의 수 탐색에 필수적입니다. 트리 구조 처리: 파일 시스템 탐색, DOM 트리 조작, JSON 파싱 등에 활용됩니다. 분할 정복 알고리즘: 병합 정렬, 퀵 정렬, 이진 탐색 등 효율적인 알고리즘의 기초가 됩니다. 동적 프로그래밍: 복잡한 최적화 문제를 재귀와 메모이제이션으로 해결합니다. 코딩 테스트에서는 DFS/BFS, 백트래킹, 동적 프로그래밍 문제가 자주 출제되므로 재귀 함수 마스터하기는 필수 역량입니다.

마무리

재귀 함수 마스터하기는 단순히 문법을 익히는 것을 넘어, 문제를 분할하고 해결하는 사고방식을 키우는 과정입니다. 종료 조건과 재귀 케이스를 명확히 정의하고, 필요에 따라 메모이제이션이나 꼬리 재귀 최적화를 적용하면 강력하고 효율적인 코드를 작성할 수 있습니다. 처음에는 어렵게 느껴질 수 있지만, 다양한 예제를 직접 구현해보면서 재귀적 사고를 체득한다면 어떤 복잡한 문제도 해결할 수 있는 실력을 갖추게 될 것입니다.