費氏數列
費氏數列 的公式為 Fn = Fn-1 + Fn-2。換句話說，下一個數字是前兩個數字的總和。
前兩個數字為 1，然後為 2(1+1)，再接下來為 3(1+2)、5(2+3)，以此類推：1, 1, 2, 3, 5, 8, 13, 21...。
費氏數列與黃金比例以及我們周遭許多自然現象有關。
撰寫一個函式 fib(n)，用來傳回第 n 個費氏數列。
範例操作
function fib(n) { /* your code */ }
alert(fib(3)); // 2
alert(fib(7)); // 13
alert(fib(77)); // 5527939700884757附註：函式必須快速。呼叫 fib(77) 應該不會花費超過一秒鐘的一小部分時間。
我們可以嘗試的第一個解法是遞迴。
費氏數列的定義就是遞迴
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) 將會被呼叫並評估兩次，而且完全獨立。
以下是完整的遞迴樹
我們可以清楚地注意到 fib(3) 被評估兩次，而 fib(2) 被評估三次。總計算量會比 n 成長得快很多，即使 n=77 也會變得非常龐大。
我們可以透過記住已經評估過的值來最佳化它：如果說 fib(3) 的值已經計算過一次，那麼我們就可以在未來的計算中重複使用它。
另一個變體是放棄遞迴，並使用完全不同的基於迴圈的演算法。
我們可以從 n 開始，而不是從 n 往下到較小的值，我們可以建立一個從 1 和 2 開始的迴圈，然後將 fib(3) 作為它們的總和，然後將 fib(4) 作為前兩個值的總和，然後是 fib(5)，並一直往上，直到得到需要的數值。在每一步，我們只需要記住前兩個值。
以下是新演算法的詳細步驟。
開始
// 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 開始，因為第一個和第二個序列值被硬編碼到變數 a=1、b=1 中。
這種方法稱為 動態規劃自底向上。