費波那契數列實作及優化

[LeoWangJ]

費波那契數列實作

先看一下維基百科的費波那契解釋：

F0 = 0 F1 = 1 Fn = F(n-1) +F(n-2)（n≧2） 用文字來說，就是費氏數列由0和1開始，之後的斐波那契系數就是由之前的兩數相加而得出。 ex: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233....... 0代表第0項 簡單來說就是第一項與第二項相加就為第三項的值。
讓我們來看程式是怎麼寫的：

let fib = (n) => 
n === 0 ? 0 : 
n === 1 ? 1  :
fib(n-1) + fib(n-2)

fib(4) // 3

上面的例子意思是說, 假如n是0則返回0，若是1則返回1，若都不是則返回下兩項的相加。  
但是使用遞迴有一個問題就是當傳入的參數越大則計算時間會變非常的久。

```js
console.time('時間1')
fib(40)  // 花了2230.783935546875ms
console.timeEnd('時間1')

console.time('時間2')
fib(45) //花了25279.218017578125ms
console.timeEnd('時間2')

fib(40與fib(45)的計算足足差了23秒，這是因為遞迴雖然裡面有一些函數我們已經計算過了但是電腦沒有那麼聰明，所以還是會重複計算，所以有人發明尾遞迴來優化。

尾遞迴優化

尾遞迴的思路是我們從前面第二項開始計算到要計算的那一個項目，並且將計算完的第一項與第二項函式的參數一起傳到執行的參數中。

fib = (n) => fib_inner(2,n,1,0)
/*
 * start - 起始項目
 * end - 結束項目
 * prev1 - 計算的第一項
 * prev2 - 計算的第二項
 */
fib_inner = (start, end , prev1, prev2) => 
    start === end ? prev1 + prev2 :
           fib_inner(start + 1, end , prev1 + prev2, prev1 )

上面fib_inner 的意思就是當起始項目與最後要計算的項目相等時，就將計算好的第一項與第二項的值相加，否則就繼續執行下一個起始項目並且將下一個起始項目的第一項改成上一個第一項與第二項相加，第二項變成上一個第一項。

用文字敘述可能看不太懂，我們用數字n= 3 帶入進去：

fib(3) // 呼叫
fib = (3) => fib_inner(2,3,1,0) // n = 3

fib_inner = (2, 3 , 1, 0) => 
    2 === 3 ? 1 + 0 :  // 不相等
           fib_inner(2 + 1, 3 , 1 + 0, 1 ) //  此時fib(2+1)的prev1 已經變成 1 + 0, prev2 變成 1

又在執行  fib_inner(2 + 1, 3 , 1 + 0, 1 )

 fib_inner(2 + 1, 3 , 1 + 0, 1 ) => 
       ( 2 +1) === 3 ?  (1 + 0) + 1 :  // 相等
           fib_inner(3 + 1, 3 , 1 + 1, 1 ) // 不執行

將數值帶入進去後應該就會明白他的意思是什麼了。
那麼真的有比較快嗎？

console.time('時間2')
fib(45) // 0.07421875ms
console.timeEnd('時間2')

比我們剛剛用遞迴快了超級多！