JavaScriptで学ぶフィボナッチ数列：素朴な再帰からメモ化（動的計画法）への最適化

フィボナッチ数とは

フィボナッチ数とは、「最初の2つの数以降、各項がその直前の2つの数の和になる」という性質を持つ数列のことです。数列は 1, 1 から始まります。

1, 1, 2, 3, 5, 8, 13, 21, 34, …

素朴な再帰による実装

n番目のフィボナッチ数を求めるプログラムは、シンプルには次のように書けます。

function fibNaive(n) {
    if (n <= 1) return n;
    return fibNaive(n - 1) + fibNaive(n - 2);
}

実際に動かして確認してみましょう。

console.log(fibNaive(7));
console.log(fibNaive(8));
console.log(fibNaive(9));
console.log(fibNaive(4));

実行結果は以下の通りです。

13
21
34
3

関数呼び出しの流れとパフォーマンスの問題点

f(5) を呼び出したとき、内部では次のように関数呼び出しが木構造状に展開されていきます。

/**
 *             f(5)
 *           /      \
 *        f(4)       f(3)
 *       /    \     /    \
 *     f(3)  f(2)  f(2)  f(1)
 *     /  \    ..........
 *   f(2) f(1) ..........
 */

この図を見ると分かるように、f(5) の呼び出し1回の中で、f(2) はおよそ4回も計算されています。同じコードが何度も繰り返し実行されるこの状態は、重複する部分問題（overlapping subproblem）の典型例です。試しに n = 500 を渡して実行すると、膨大な数の呼び出しが発生し、処理が事実上完了しなくなってしまうでしょう。

動的計画法（メモ化）による改善

5番目のフィボナッチ数が必要なとき、本来はそれより小さいフィボナッチ数を「それぞれ1回だけ」計算すれば十分なはずです。しかし素朴な再帰では、同じ値を何度も再計算してしまいます。そこで、一度計算した値をどこかに保存しておき、再利用することで冗長な計算を排除できます。これこそが動的計画法（Dynamic Programming）の核心的な考え方です。

一度計算して、あとで再利用する。

メモ化を使った fib 関数の実装を見てみましょう。

let fibStore = {};
function fibDP(n) {
    if (n <= 1) return n;
    if (fibStore[n]) {
        return fibStore[n];
    }
    fibStore[n] = fibDP(n - 1) + fibDP(n - 2);
    return fibStore[n];
}

ここでは fibStore というオブジェクトをキャッシュとして使い、すでに計算済みの値を記録しています。これにより過剰な重複計算が大幅に削減され、関数は効率的に動作します。

同じコードでテストしてみます。

console.log(fibDP(7));
console.log(fibDP(8));
console.log(fibDP(9));
console.log(fibDP(4));

実行結果：

13
21
34
3

メモ化版であれば、非常に大きな n の値でも高速に計算できます。ぜひ大きな数値を渡して、その違いを体感してみてください。