[JavaScript] 재귀와 스택의 동작 원리

재귀의 기본 개념

재귀는 함수가 자기 자신을 호출하여 문제를 더 작은 동일 문제로 분할하고 해결하는 프로그래밍 기법입니다. 문제를 분할하기 때문에 복잡한 문제를 단순화하여 해결할 수 있게 해줍니다.

• 베이스 케이스 : 재귀 호출을 멈추는 단계로 더이상 분할이 필요하지 않습니다. 예) factorial(1) = 1
• 재귀 단계 : 문제를 더 작은 부분으로 나누어 함수를 다시 호출하는 단계 예) factorial(n) = n * factorial(n-1)

재귀 함수 예제: 팩토리얼

팩토리얼 함수는 자연수 n에 대해 n! = n × (n-1) × … × 1을 계산하는 대표적인 재귀 예제입니다.

function factorial(n) {
  // 베이스 케이스: n이 1 이하이면 팩토리얼은 1입니다.
  if (n <= 1) {
    return 1;
  }
  // 재귀 단계: n! = n * (n-1)!
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 120 (5 * 4 * 3 * 2 * 1)

재귀 호출 과정

• factorial(5)는 5 * factorial(4)를 반환
• factorial(4)는 4 * factorial(3)를 반환
• factorial(3)는 3 * factorial(2)를 반환
• factorial(2)는 2 * factorial(1)를 반환
• factorial(1)는 1을 반환 (베이스 케이스)

최종 베이스 케이스의 결과(1)로부터 거꾸로 곱해져 최종 결과(120)를 도출합니다.

실행 컨텍스트와 콜 스택

재귀 호출이 발생할 때마다 새로운 실행 컨텍스트가 생성되어 콜 스택에 쌓입니다.

위 예제에서의 실행 컨텍스트는 아래와 같이 쌓입니다.

• Context: { n: 5 }
• Context: { n: 4 }
• Context: { n: 3 }
• Context: { n: 2 }
• Context: { n: 1 }

각 함수 호출이 완료되면, 해당 컨텍스트는 스택에서 pop되어 이전 컨텍스트로 제어권이 돌아갑니다. 이러한 방식으로 스택에 쌓이는 호출 깊이가 재귀 깊이를 결정하며, 메모리 사용량에 영향을 줍니다.

재귀 호출이 너무 깊어지면 스택 오버플로우(stack overflow)가 발생하여 "Maximum call stack size exceeded" 오류가 나타납니다.

재귀적 자료 구조와 순회

재귀는 트리 구조와 같은 재귀적 자료 구조를 탐색하거나 처리할 때 특히 효과적입니다.

파일 시스템 디렉토리 트리 순회

const fileSystem = {
  name: "root",
  files: ["file1.txt", "file2.txt"],
  folders: [
    {
      name: "sub1",
      files: ["file3.txt"],
      folders: []
    },
    {
      name: "sub2",
      files: [],
      folders: [
        {
          name: "sub2_1",
          files: ["file4.txt"],
          folders: []
        }
      ]
    }
  ]
};

function listFiles(node, path = "") {
  const currentPath = `${path}/${node.name}`;
  node.files.forEach(file => {
    console.log(`${currentPath}/${file}`);
  });
  node.folders.forEach(folder => {
    listFiles(folder, currentPath);
  });
}

listFiles(fileSystem);
// 출력:
// /root/file1.txt
// /root/file2.txt
// /root/sub1/file3.txt
// /root/sub2/sub2_1/file4.txt

재귀 대 반복문

재귀 사용 시

• 코드가 수학적 정의에 가깝고 직관적입니다.
• 재귀 깊이에 따른 스택 사용에 주의해야 합니다.

반복문 사용 시

• 일반적으로 메모리 사용이 일정하며, 스택 오버플로우의 위험이 없습니다.
• 복잡한 반복문은 가독성을 떨어뜨릴 수 있습니다.

팩토리얼 반복문으로 변환

function factorialIterative(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

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