JavaScriptでアッカーマン数を計算する方法(再帰関数の実装例)

アッカーマン関数とは

アッカーマン関数(Ackermann Function)は、再帰関数の古典的な例として知られる数学関数です。最大の特徴は、原始再帰関数ではないという点にあります。これは、for文やwhile文のような単純なループ処理だけでは表現できないことを意味します。

また、この関数は入力値の増加に対して値が極めて急速に大きくなることでも有名です。値の増大に伴い、再帰呼び出しのツリー(コールスタック)も爆発的に深くなるため、再帰の挙動や計算量の理論を学ぶ題材としてよく取り上げられます。

問題

2つの数 m と n を第1引数・第2引数として受け取るJavaScript関数を作成します。この関数は、以下の定義に従ってアッカーマン数 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 のとき)

実装例

上記の定義をそのまま再帰処理として書き下したのが、次のJavaScriptコードです。

const m = 2;
const n = 3;

const ackermann = (m, n) => {
    if (m === 0) {
        return n + 1;
    }
    if (n === 0) {
        return ackermann(m - 1, 1);
    }
    return ackermann(m - 1, ackermann(m, n - 1));
};

console.log(ackermann(m, n)); // 出力: 9

この例では A(2, 3) = 9 が出力されます。条件分岐の構造が数学的な定義とほぼ1対1に対応しているため、再帰関数の基本的な考え方を理解するのに最適なサンプルといえます。

注意点:爆発的な計算量

アッカーマン関数の値は、入力が少し大きくなるだけで天文学的な規模に達します。例えば A(4, 2) は 2⁶⁵⁵³⁶ − 3(約10の19728乗)という巨大な数になります。そのため、m = 12 のような大きな値を指定すると、現実的な時間内に計算が完了しません。

さらに、深い再帰呼び出しによって「Maximum call stack size exceeded」というスタックオーバーフローエラーが発生する可能性もあります。動作確認を行う場合は、m ≤ 3 程度の小さな値にとどめておくのが安全です。