자바스크립트로 두 수에 대한 아커만 수(Ackermann Number) 계산하기

아커만 함수(Ackermann Function)란?

아커만 함수는 재귀 함수의 대표적인 예제로, 특히 원시 재귀 함수(primitive recursive function)가 아니라는 점에서 유명합니다. 이 함수는 입력값이 조금만 커져도 결과값이 기하급수적으로 폭발적으로 증가하며, 호출 트리(call tree)의 크기 역시 매우 빠르게 커지는 특징이 있습니다.

이러한 특성 때문에 아커만 함수는 재귀 호출의 동작 방식을 이해하거나, 프로그래밍 언어의 스택 오버플로우 한계를 테스트하는 용도로 자주 활용됩니다.

문제 정의

두 개의 숫자 m과 n을 인수로 받는 자바스크립트 함수를 작성해야 합니다. 이 함수는 다음과 같이 정의되는 아커만 수 A(m, n)를 반환해야 합니다.

A(m,n) = n+1                (m = 0일 때)
A(m,n) = A(m-1, 1)          (m > 0, n = 0일 때)
A(m,n) = A(m-1, A(m, n-1))  (m > 0, n > 0일 때)

구현 예제

위의 수학적 정의를 그대로 코드로 옮기면 다음과 같습니다. 세 가지 조건 분기를 화살표 함수(arrow function)를 사용해 간결하게 구현할 수 있습니다.

const m = 2;
const n = 3;

const ackermann = (m, n) => {
    // m이 0이면 n + 1을 반환
    if (m === 0) {
        return n + 1;
    }
    // m이 0보다 크고 n이 0이면 A(m-1, 1)을 재귀 호출
    if (n === 0) {
        return ackermann(m - 1, 1);
    }
    // m과 n이 모두 0보다 크면 중첩 재귀 호출
    if (m !== 0 && n !== 0) {
        return ackermann(m - 1, ackermann(m, n - 1));
    }
};

console.log(ackermann(m, n)); // 출력: 9

코드 설명 및 주의사항

위 코드는 아커만 함수의 세 가지 경우를 순서대로 처리합니다.

• m = 0인 경우: 단순히 n + 1을 반환하며 재귀가 종료됩니다.
• n = 0인 경우: A(m-1, 1)을 호출하여 문제를 더 작은 크기로 줄입니다.
• m, n이 모두 양수인 경우: A(m-1, A(m, n-1))처럼 재귀 호출의 결과를 다시 인수로 사용하는 중첩 구조가 됩니다.

예를 들어 A(2, 3)은 9를 반환하지만, A(4, 2)는 19,729라는 매우 큰 값이 되며, A(5, 5)는 사실상 계산이 불가능한 수준으로 증가합니다. 따라서 실제 테스트 시에는 작은 값의 m과 n을 사용하는 것이 좋습니다. 또한 깊은 재귀 호출로 인해 브라우저나 Node.js 환경에서 스택 오버플로우(Stack Overflow)가 발생할 수 있으므로 주의해야 합니다.