ここでは、「メモ化（memoization）」を使って再帰関数を高速化する方法を、
ステップ実行（呼び出しの流れを1つずつ追う）つきでわかりやすく解説します。
そもそも「メモ化」とは？
メモ化（memoization）とは
一度計算した結果を「メモ（記憶）」しておき、
同じ入力が来たときに再計算せずに結果を返す仕組み。
再帰では同じ計算を何度も行ってしまうことがよくあります。
これを防げばスピードが大幅に上がります！
例：フィボナッチ数列（遅い再帰）
まず、メモ化なしの再帰から：
function fib(n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
console.time("slow");
console.log(fib(40)); // 結果: 102334155（数秒かかる）
console.timeEnd("slow");
この fib(40) は、なんと 約3千万回以上 関数を呼び出しています。
なぜなら、同じ値を何度も再計算しているからです。
改善：メモ化（記憶）付きの再帰
では、同じ計算を二度しないように、結果を**保存（キャッシュ）**しておきましょう。
function fibMemo(n, memo = {}) {
// ① すでに計算済みならそれを返す
if (n in memo) return memo[n];
// ② ベースケース
if (n <= 1) return n;
// ③ 結果を保存してから返す
memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
return memo[n];
}
console.time("fast");
console.log(fibMemo(40)); // 結果: 102334155（瞬時に終わる）
console.timeEnd("fast");
💡 結果
fib(40) → 数秒
fibMemo(40) → ほぼ一瞬！
なぜ速くなった？
→ 同じ値（例：fib(35)など）を2回目以降は再計算せず、
保存しておいた結果をすぐ返すからです。
ステップ実行で「呼び出しの流れ」を追う
内部の動きを目で追ってみましょう👇
function fibMemoTrace(n, memo = {}) {
console.log(`呼び出し: fib(${n})`);
if (n in memo) {
console.log(` → メモから取得: fib(${n}) = ${memo[n]}`);
return memo[n];
}
if (n <= 1) {
console.log(` → ベースケース: fib(${n}) = ${n}`);
return n;
}
const result =
fibMemoTrace(n - 1, memo) + fibMemoTrace(n - 2, memo);
memo[n] = result;
console.log(`計算完了: fib(${n}) = ${result}`);
return result;
}
fibMemoTrace(5);
📜 出力（抜粋）：
呼び出し: fib(5)
呼び出し: fib(4)
呼び出し: fib(3)
呼び出し: fib(2)
呼び出し: fib(1)
→ ベースケース: fib(1) = 1
呼び出し: fib(0)
→ ベースケース: fib(0) = 0
計算完了: fib(2) = 1
呼び出し: fib(1)
→ ベースケース: fib(1) = 1
計算完了: fib(3) = 2
呼び出し: fib(2)
→ メモから取得: fib(2) = 1
計算完了: fib(4) = 3
呼び出し: fib(3)
→ メモから取得: fib(3) = 2
計算完了: fib(5) = 5
ポイント整理
| 処理内容 | 意味 |
|---|---|
if (n in memo) | すでに計算した値があるなら、それを返す |
if (n <= 1) | ベースケース（再帰終了） |
memo[n] = ... | 計算結果を保存 |
return memo[n] | 次回以降は再計算しない |
応用：再帰のメモ化テンプレート
再帰で計算を高速化したいときは、このパターンを使えばOKです👇
function memoized(fn) {
const cache = {};
return function(...args) {
const key = JSON.stringify(args);
if (cache[key]) return cache[key];
const result = fn(...args);
cache[key] = result;
return result;
};
}
// 使用例：
const fibFast = memoized(function fib(n) {
if (n <= 1) return n;
return fibFast(n - 1) + fibFast(n - 2);
});
console.log(fibFast(40)); // 超高速！
これで「どんな再帰関数」でもメモ化付きにできます。
まとめ
| 比較 | メモ化なし | メモ化あり |
|---|---|---|
| fib(40) の速度 | 数秒〜十数秒 | ほぼ一瞬 |
| 計算回数 | 数千万回 | 約40回 |
| メモリ使用量 | 少ない | 少し多い（結果を保存するため） |
| 向いている問題 | 計算量が少ない再帰 | 同じ計算を何度もする再帰 |
次にやってみると良い発展テーマ：
- 🪜 メモ化付きで「階乗」「組み合わせ（nCr）」を高速化する
- 🌳 メモ化を使って「ツリー探索でのキャッシュ」を実装する
- 🧩 メモ化と「クロージャ」を組み合わせて汎用キャッシュ関数を作る