では「フィボナッチ数列」を題材に、再帰版とループ版を比較してみましょう。これで「再帰の弱点」と「工夫の仕方」がよく見えてきます。
フィボナッチ数列の定義
- ( F(0) = 0, ; F(1) = 1 )
- ( F(n) = F(n-1) + F(n-2) ) （n ≥ 2 のとき）
つまり：0, 1, 1, 2, 3, 5, 8, 13, …
再帰版（素直な実装）
function fibRec(n) {
if (n === 0) return 0;
if (n === 1) return 1;
return fibRec(n - 1) + fibRec(n - 2);
}
console.log(fibRec(10)); // 55
👉 定義そのままで直感的。
👉 ただし 同じ計算を何度も繰り返す ため、nが大きいと爆発的に遅くなる。
例: fibRec(40) を呼ぶと数億回の計算になる。
ループ版（効率的）
function fibLoop(n) {
if (n === 0) return 0;
if (n === 1) return 1;
let a = 0, b = 1;
for (let i = 2; i <= n; i++) {
const next = a + b;
a = b;
b = next;
}
return b;
}
console.log(fibLoop(10)); // 55
👉 ループで前の2つの値を持ち回るだけ。
👉 計算量は O(n)、メモリも O(1)。大きな n でも高速。
改良版：メモ化再帰
「再帰の直感性」と「ループの効率」を両立する方法が メモ化。
function fibMemo(n, memo = {}) {
if (n in memo) return memo[n];
if (n === 0) return 0;
if (n === 1) return 1;
memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
return memo[n];
}
console.log(fibMemo(50)); // 12586269025
👉 計算済みの結果を保存して再利用するので、効率が劇的に改善。
✅ まとめ
| 方法 | 特徴 |
|---|---|
| 再帰（素直） | 定義通りで分かりやすいが、計算が爆発的に増える |
| ループ | 高速・省メモリ、実務でよく使われる |
| メモ化再帰 | 再帰の直感性を保ちつつ効率化できる |
👉 ここまでで「階乗」「配列合計」「ネスト配列」「探索」「ソート」「フィボナッチ」と幅広く再帰を見てきました。
