フィボナッチ数とメモ化

メモ化は関数の結果を保存し、同じ引数への再要求を検索で答えます。フィボナッチ数は fib(n) = fib(n-1) + fib(n-2)、基底は fib(0) = 0、fib(1) = 1。素朴な再帰は同じ部分問題を繰り返して指数的に呼び出しが増え、キャッシュなら O(n) 状態の計算で済みます。

同じ小計を毎回作り直す計算係に、結果のノートを渡す形です。一度計算し、その後は参照します。素朴な再帰、トップダウンのメモ化、ボトムアップの表を比較します。

メモ化の仕組み

既定の素朴な再帰は fib(6) から fib(5) と fib(4) を呼び、fib(1) と fib(0) まで分けます。記録がないので同じ fib(4) の部分木も再構築します。

トップダウンのメモ化は同じ再帰に memo 辞書を加えます。最初の fib(4) を保存すれば、次は期待 O(1) のヒットで答え、部分木を展開しません。

ボトムアップは再帰を使いません。dp[0] = 0、dp[1] = 1 の後、dp[i] = dp[i-1] + dp[i-2] を順に書きます。一セル一書き込みで、前二セルは完成済みです。

答えは同じです。素朴版は重複を無視し、メモ化は必要時に計算し、表は依存順に計算します。

計算をステップで追う

既定は素朴な再帰、n = 6、目標 fib(6) = 8。

1. fib(6) を呼ぶ：fib(5) + fib(4) が必要で、先に fib(5) へ。
2. 左へ深く進む：fib(5) → fib(4) → fib(3) → fib(2)、最後に fib(1) = 1 と fib(0) = 0。
3. 上へ合成：combine で fib(2) = 1 + 0 = 1、別の return で渡す。続いて fib(3) = 1 + 1 = 2、fib(4) = 2 + 1 = 3、fib(5) = 3 + 2 = 5。
4. fib(4) を再計算：根の第二の子が残る。記憶がないので九呼び出しの部分木を再展開し、状態表示が同じ引数の再登場を示す。
5. 完了：fib(6) = 5 + 3 = 8、合計 25 呼び出し。

Memoization は同じ入力を 11 呼び出しで解きます。fib(2)、fib(3)、fib(4) の再要求がキャッシュヒットになり、枝を作りません。Bottom-up では木がなく、表に 0, 1, 1, 2, 3, 5, 8 を書きます。漸化式のセルを選択し、前二セルを読み、和を保存します。

木は呼び出しごとにノードを出し、合成時に二つの子を加数として強調し、返却値で緑になります。メモ欄は store で行を追加し、ヒットで点灯します。25 対 11 のカウンターが省いた仕事です。

時間・空間計算量

φ は約 1.618。素朴な呼び出し数も指数的に増え、n = 50 では多数の再計算を行いますが、DP の状態数は線形です。任意精度整数では加算費用と各値のビット数も数える必要があり、表の単位費用モデルを無限に大きい値へそのまま適用できません。

境界ケース

• n = 0、1：即返却し再帰しない。スライダーは 2–7 で、7 の素朴木はすでに 41 ノード。
• 基底はキャッシュしない：表示コードは memo より先に n < 2 を検査し、0 と 1 はヒットにならない。
• Python の memo={}：デフォルト辞書は呼び出し間で共有される。独立キャッシュが必要なら別に作る。
• 大きい n：固定幅整数は実行回数より先にオーバーフローが問題になる場合がある。

よくある間違い

• 小入力だけで素朴版の拡張性を判断する。 正解でも、小さい n は指数費用を隠します。
• 基底とキャッシュの順を変えて同じトレースを期待する。 ここでは基底を先に返します。別の一貫した順序も正しく作れますが、ヒット・保存・終了経路が変わります。
• 表の長さを一つ誤る。 一般の漸化式には n + 1 セルと dp[0]、dp[1] が必要です。n = 0 は特別に処理し、二セル目を範囲外に書かないでください。
• メモ化が答えを変えると思う。 変えるのは仕事量だけです。