재귀의 종료 조건: 작은 문제와 기저 조건으로 거듭제곱 계산하기

재귀는 같은 모양의 더 작은 문제를 함수에 맡기는 방법입니다. 멈출 답을 먼저 정하고, 모든 재귀 호출이 그 답에 가까워지도록 만들어야 합니다.

선수 지식: 함수 호출과 반환값, if 조건문, 0 이상의 정수와 거듭제곱의 의미

• 재귀식과 기저 조건을 나누어 설명합니다.
• 입력 크기가 줄어드는지 확인하여 종료를 판단합니다.
• 수학적 종료와 JavaScript 실행 한계를 구분합니다.

2의 세제곱에서 하나의 곱셈을 떼어 내기

2³은 2를 세 번 곱한 값입니다. 마지막 2 하나를 떼면 2² × 2로 쓸 수 있습니다. 제곱을 구하는 방법을 이미 안다고 가정하면, 현재 함수가 남겨 둘 일은 작은 답에 2를 곱하는 한 단계뿐입니다. 이 관계를 power(x, n) = power(x, n - 1) × x로 나타냅니다.

여기서 작은 문제는 밑이 작은 문제가 아니라 지수가 하나 줄어든 문제입니다. 밑 x는 그대로 두고 n만 줄여야 처음 맡은 거듭제곱과 연결됩니다. power(2, 3)에서 무조건 power(1, 2)를 부르면 종료하더라도 다른 값을 계산하게 됩니다. 줄일 값과 유지할 값을 구분하는 것이 재귀 설계의 출발점입니다.

지수 0에서는 더 곱할 2가 없습니다. 곱셈을 이어 붙일 때 결과를 바꾸지 않는 값이 1이므로 power(x, 0)은 1을 반환합니다. 이 예제에서는 power(0, 0)도 같은 규칙에 따라 1로 정합니다. 해당 규칙은 이 함수의 입력 계약이며, 모든 맥락에서 0의 0제곱을 정의한다는 뜻은 아닙니다.

호출은 내려가고 곱셈은 돌아오며 끝납니다

호출이 만들어지는 순서와 답이 완성되는 순서는 반대입니다. 지수 3인 함수는 지수 2의 반환값을 받을 때까지 끝나지 않습니다. 기저 조건에서 1을 반환한 뒤에야 1 × 2, 2 × 2, 4 × 2가 차례로 계산됩니다. 따라서 함수 첫 줄에서 어떤 값을 출력하는지와 반환값이 무엇인지는 별도로 읽어야 합니다.

멈출 조건과 그 조건에 도달할 조건은 다릅니다

n === 0이라는 조건만 있다고 재귀가 항상 멈추지는 않습니다. n이 -1이면 다음 호출은 -2가 되어 0에서 더 멀어집니다. 1.5도 0.5, -0.5로 바뀌어 정확한 0에 도달하지 않습니다. 이 함수는 재귀를 시작하기 전에 지수가 0 이상인 정수인지 검사합니다. 허용한 입력에서는 n이 매번 1씩 줄고 음수가 되기 전에 0을 만나므로 종료가 설명됩니다.

코드의 지수 상한 256은 학습 예제를 작게 유지하려는 제한입니다. 모든 JavaScript 환경의 최대 재귀 깊이가 256이라는 의미는 아닙니다. 실행 환경과 함수가 사용하는 스택 공간에 따라 한계가 달라지므로 아주 큰 지수를 처리할 일반 함수라면 반복문이나 제곱 분할 방식으로 설계를 바꾸는 편이 좋습니다.

밑은 유한한 Number만 받으며 계산 중 Infinity가 나오면 오류로 알립니다. 이 검사로 부동소수점 반올림까지 없어지지는 않습니다. 예를 들어 소수의 거듭제곱은 표현 가능한 근삿값이 될 수 있습니다. 재귀 구조를 배우는 동안에는 작은 정수로 호출 관계를 확인한 뒤 수 표현의 조건을 따로 넓히는 것이 좋습니다.

기저 조건은 결과의 의미와 비용을 함께 결정합니다

기저 조건을 0으로 반환하면 모든 복귀 단계가 0 × x가 되어 답이 모두 0이 됩니다. 기저 조건은 단순한 비상 탈출문이 아니라, 작은 문제의 정확한 답입니다. 더하기 재귀에서 빈 합이 0인 것과 곱하기 재귀에서 빈 곱이 1인 것을 비교하면 왜 문제마다 다른 값을 반환하는지 알 수 있습니다.

문제를 처음 설계할 때는 바로 답할 수 있는 가장 작은 입력을 적고, 그 답과 한 단계 큰 입력을 연결해 보세요. 곱할 값 하나를 보태도 원래 의미가 유지되는지 확인하면 종료만 하는 함수와 올바른 답을 계산하는 함수를 구분할 수 있습니다.

지수 n을 기준으로 호출은 n + 1번, 곱셈은 n번 발생하므로 시간은 O(n)입니다. 아래쪽 답을 기다리는 호출도 n개 정도 쌓여 추가 공간은 O(n)입니다. 소스에 반복문이 없다는 사실만 보고 시간이나 공간이 상수라고 판단하면 안 됩니다. 실제로 반복되는 호출 수와 동시에 살아 있는 호출 수를 각각 세어야 합니다.

전체 코드와 직접 실행

개념을 읽었다면 아래 예제를 직접 실행하며 상태 변화를 확인할 수 있습니다.

function power(base, exponent) {
  if (!Number.isFinite(base)) throw new TypeError('밑은 유한한 숫자여야 합니다.');
  if (!Number.isInteger(exponent) || exponent < 0 || exponent > 256) {
    throw new RangeError('지수는 0부터 256까지의 정수여야 합니다.');
  }
  function solve(n) {
    if (n === 0) return 1;
    const result = solve(n - 1) * base;
    if (!Number.isFinite(result)) throw new RangeError('Number 범위를 벗어났습니다.');
    return result;
  }
  return solve(exponent);
}

console.log(power(2, 3));
console.log(power(5, 0));
console.log(power(-2, 3));

node javascript-recursion-base-case.mjs

8
1
-8

비용과 적용 범위

시간: O(n)

공간: O(n)

분석 조건: n은 지수이며 예제는 0~256의 정수만 받습니다. Number 곱셈을 상수 시간으로 세고, 대기 중인 호출 스택을 추가 공간에 포함합니다.

직접 확인해 보기

power(3, 2)가 호출하는 지수를 순서대로 적고, 기저 조건에서 1 대신 0을 반환하면 최종 값이 무엇인지 설명해 보세요.

함께 읽을 글

• 기초 구현 패턴: 조건·정수 계산·순회·상태 갱신 — 조건문과 상태를 줄이는 기본 구현 방법을 복습합니다.
• 자료구조 스택 쉽게 이해하기: push pop으로 문제 풀이 감 잡기 — 뒤에 들어간 호출이 먼저 돌아오는 순서를 스택과 연결합니다.

참고 자료

• MDN JavaScript Guide: Functions — 자기 자신을 호출하는 함수와 재귀 호출의 중첩, 기저 조건을 참고했습니다. 호출·복귀 추적과 입력 계약은 별도로 구성했습니다.
• MDN Glossary: Call stack — 실행 중인 함수 호출을 쌓고 반환할 때 제거하는 호출 스택, 지나친 중첩의 제한을 참고했습니다.