재귀 함수

항상 헷갈리는 재귀 함수… 재귀가 무엇인지, 메모리 상에서 어떻게 동작하는지, 그리고 언제 사용하는 것이 효율적인지에 대해 알아봅시다.

재귀 함수란?

재귀 함수는 자기 자신을 반복적으로 호출하는 함수입니다. (이름 그대로의 재귀 호출 함수) 동적 프로그래밍이나 분할 정복 알고리즘에 있어 필수적인 개념이에요.

메모리 동작 원리 (Stack)

함수가 호출될 때마다 메모리(스택) 상에 새로운 함수 덩어리가 생성되어 쌓입니다

function factorial(n) {
    // 종료 조건
    if (n <= 1) {
        return 1;
    }
    
    // 재귀 호출 부분
    return n * factorial(n - 1);
}

// 사용 예시
const num = 5;
const result = factorial(num);

console.log(`${num}! = ${result}`); // 출력: 5! = 120

factorial(3) 이 있다고 가정하면

1. 1.factorial(3) 호출: 3 * factorial(2)
2. 2.factorial(2) 호출: 2 * factorial(1)
3. 3.factorial(1) 호출: 종료 조건(n <= 1)에 도달하여 1을 반환하며 함수 종료.
4. 4.factorial(2)로 돌아와 2 * 1을 계산하고 2 반환.
5. 5.factorial(3)으로 돌아와 3 * 2를 계산하고 6을 최종 반환.

종료 조건 및 리턴

재귀 함수는 반드시 무한 호출을 막기 위한 종료 조건을 포함해야 합니다. 종료 조건이 없으면 콜 스택 오버플로우로 인해 프로그램이 다운됩니다.

종료 조건(n=0)에 도달하면 return을 통해 호출했던 곳으로 돌아가며 (역순으로) 함수가 종료됩니다

코드 수행 시점

재귀 호출 위에 있는 구문은 호출이 이루어지기 전에 수행됩니다 (예: 재귀함수 위에 있으면 5, 4, 3, 2, 1순으로 출력)

재귀 호출 아래에 있는 구문은 모든 호출이 끝나고 리턴되어 돌아오면서 (역순으로) 수행됩니다 (재귀 아래에 있으면 1, 2, 3, 4, 5 순으로 출력)

재귀 함수 사용의 효율성

대부분의 재귀 함수는 반복문(루프)으로 표현할 수 있습니다.

재귀 함수는 호출될 때마다 메모리를 많이 사용하기때문에, 호출 및 리턴 과정으로 인해 반복문보다 실행 성능이 떨어집니다 .

따라서 재귀적인 사고방식을 가진 수학 문제, 그리고 트리나 그래프 같은 자료구조를 다룰 때처럼, 재귀를 사용했을 때 매우 쉽게 해결되는 문제에 사용하는 것이 좋습니다.

기본 템플릿

재귀 문제는 패턴이 거의 똑같아요.

function 재귀함수(tree) {
  // 1. 멈추는 조건 (기저 조건)
  if (tree.children.length === 0) {
    return 기본값;
  }

  // 2. 결과를 모을 곳
  let result = 초기값;

  // 3. 자식들에게 물어보기
  for (let child of tree.children) {
    let childResult = 재귀함수(child);  // 똑같은 함수!// childResult를 result에 반영
  }

  // 4. 내 결과 반환
  return 내계산(result);
}

흐름 보고 이해하기

function mystery(n) {
  if (n === 0) return 1;
  return 2 * mystery(n - 1);
}

console.log(mystery(3));

-----------------------------

mystery(3)
  = 2 * mystery(2)
  = 2 * (2 * mystery(1))
  = 2 * (2 * (2 * mystery(0)))
  = 2 * (2 * (2 * 1))  ← return 1
  = 2 * (2 * 2)
  = 2 * 4
  = 8