フィボナッチ数

フィボナッチ数の数列は、F_n = F_n-1 + F_n-2という公式を持ちます。言い換えれば、次の数は前の2つの数の合計です。

最初の2つの数は1で、次は2(1+1)、次は3(1+2)、5(2+3)などと続きます：1, 1, 2, 3, 5, 8, 13, 21...。

フィボナッチ数は黄金比や、私たちの周りの多くの自然現象に関連しています。

n番目のフィボナッチ数を返す関数fib(n)を書いてください。

動作例

          function fib(n) { /* your code */ }

alert(fib(3)); // 2
alert(fib(7)); // 13
alert(fib(77)); // 5527939700884757
        

追記: 関数は高速である必要があります。fib(77)の呼び出しは、1秒のほんの一部分で終わる必要があります。

ここで試せる最初の解決策は、再帰的なものです。

フィボナッチ数は定義上再帰的です。

function fib(n) {
  return n <= 1 ? n : fib(n - 1) + fib(n - 2);
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
// fib(77); // will be extremely slow!

…しかし、nの値が大きいと非常に遅くなります。たとえば、fib(77)は、すべてのCPUリソースを消費して、エンジンをしばらくハングアップさせる可能性があります。

これは、関数がサブコールをあまりにも多く行うためです。同じ値が何度も再評価されます。

たとえば、fib(5)の計算の一部を見てみましょう。

          ...
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
...
        

ここで、fib(3)の値がfib(5)とfib(4)の両方に必要であることがわかります。そのため、fib(3)が呼び出され、2回完全に独立して評価されます。

これが完全な再帰ツリーです。

fib(3)が2回、fib(2)が3回評価されていることが明確にわかります。計算の総量はnよりもはるかに速く増加し、n=77でも膨大になります。

すでに評価済みの値を記憶することでそれを最適化できます。たとえば、fib(3)の値が一度計算されたら、今後の計算でそれを再利用できます。

別の方法としては、再帰をやめて、まったく異なるループベースのアルゴリズムを使用する方法もあります。

nからより低い値に移動する代わりに、1と2から始まるループを作成し、次にそれらの合計としてfib(3)を取得し、次に2つの前の値の合計としてfib(4)を取得し、次にfib(5)を取得して、必要な値になるまで上方向に進むことができます。各ステップで、前の2つの値を記憶するだけで済みます。

これが新しいアルゴリズムの詳細な手順です。

開始

          // a = fib(1), b = fib(2), these values are by definition 1
let a = 1, b = 1;

// get c = fib(3) as their sum
let c = a + b;

/* we now have fib(1), fib(2), fib(3)
a  b  c
1, 1, 2
*/
        

ここで、fib(4) = fib(2) + fib(3)を取得したいとします。

変数をシフトしましょう。a,bはfib(2),fib(3)を取得し、cはそれらの合計を取得します。

          a = b; // now a = fib(2)
b = c; // now b = fib(3)
c = a + b; // c = fib(4)

/* now we have the sequence:
   a  b  c
1, 1, 2, 3
*/
        

次のステップでは、別の数列が得られます。

          a = b; // now a = fib(3)
b = c; // now b = fib(4)
c = a + b; // c = fib(5)

/* now the sequence is (one more number):
      a  b  c
1, 1, 2, 3, 5
*/
        

…必要な値が得られるまで続けます。これは再帰よりもはるかに高速で、重複した計算は必要ありません。

完全なコード

function fib(n) {
  let a = 1;
  let b = 1;
  for (let i = 3; i <= n; i++) {
    let c = a + b;
    a = b;
    b = c;
  }
  return b;
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
alert( fib(77) ); // 5527939700884757

ループはi=3で始まります。これは、最初と2番目の数列の値が変数a=1、b=1にハードコードされているためです。

このアプローチは、動的計画法ボトムアップと呼ばれています。