ここでトライする最初の解法は再帰的なものです。

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

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

alert( fib(3) ); // 2
alert( fib(7) ); // 13
// fib(77); // とても遅いでしょう!

…しかし、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), これらの値は定義のより 1 です
let a = 1, b = 1;

// これらの合計として get c = fib(3)
let c = a + b;

/* 今 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; // 今 a = fib(2)
b = c; // 今 b = fib(3)
c = a + b; // c = fib(4)

/* 今私たちが持っている数列:
   a  b  c
1, 1, 2, 3
*/

次のステップは別の数列を与えます:

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

/* 今、数列は次の通り:
      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 でハードコードされているためです。

このアプローチは動的計画法(dynamic programming bottom-up)と呼ばれます。