BFE.devでのAI解答例 - JavaScript コーディング問題
93. Fibonacci数をrecursionで計算する

正常に動かすのは難しいですが、再帰を使用する可能性があるアプローチについてはいくつかあります。

1. メモ化

このアプローチでは、再帰を使用してFibonacci数を計算するが、計算済みの数値を保持するキャッシュを使用して、同じ計算を複数回行わないようにすることで、計算時間を節約します。

const fib = (n, cache = {}) => {
  if (n === 0) return 0;
  if (n === 1) return 1;
  if (cache[n]) return cache[n];
  const result = fib(n - 1, cache) + fib(n - 2, cache);
  cache[n] = result;
  return result;
}

fib(10); // 55
fib(1000); // 正常に動作しない

2. 末尾再帰

このアプローチでは、末尾再帰を使用してFibonacci数を計算します。末尾再帰は、最後の操作が再帰呼び出しである再帰関数のことで、JavaScriptがこの種類の再帰を自動的にループに変換するため、スタックオーバーフローを避けることができます。

const fib = (n, a = 0, b = 1) => {
  if (n === 0) return a;
  if (n === 1) return b;
  return fib(n - 1, b, a + b);
}

fib(10); // 55
fib(1000); // 正常に動作しない

どちらのアプローチも、fib(1000)を正常に動作させることはできませんが、末尾再帰により大幅に高速化されているため、キャッシュを使用する場合のように、さまざまな入力値に対応できます。