斐波那契數列是數學領域內一個非常經典的算法問題（算法渣寫下這句話的時候都在瑟瑟發抖），今天就用五分鐘的篇幅來淺析一下這個問題。

什么是斐波那契數列？

1，1，2，3，5，8，13，21......
斐波那契數列從第三項開始，每一項都等于前兩項之和。
斐波那契數列是由數學家 Leonardoda Fibonacci 以兔子繁殖為例子而提出的，所以也叫做“兔子數列”

當然了，為了和計算機領域結合起來，這個問題會變成：實現一個函數f(n)，求斐波那契數列的第n項是多少？（n始終為正整數）

采用遞歸實現

有編程經驗的你一定會想到遞歸。好的開始是成功的一半，如果你能想到遞歸，那么離成功已經不遠了。
不難看出，數列的遞推規律可以總結為：

f(n) = f(n-1) + f(n-2) 復制代碼

okay，挽起袖子開擼

function fibonacci(num){if (num <= 2){return 1;}else{return fibonacci(num - 1) + fibonacci(num - 2);} } 復制代碼

乍一看，完美。
不過這個時候，但凡是個稍微有點追求的 Developer 都會說：“大兄弟你這么搞不是最優解呀，數字稍微大一點就炒雞慢了?！?/p>

有緩存的 Fibonacci

雖然人艱不拆，但是優化還是要做的。
我不禁想到了前端性能優化里面最常見且好用的一條：緩存。大概的思路就是，將新算出來的值保存起來以便下一次使用。
Talk is cheap, show u the code

let fibo = (function(){let cache = [];return function(n){if (cache[n] !== undefined){return cache[n];}else{return cache[n] = (n <= 2) ? 1 : fibo(n - 1) + fibo(n - 2);}} })(); 復制代碼

乍一看，又是完美。
還能優化嗎？當然。
這里用數組作為緩存容器，當計算過 fibo(50) 時，數組的長度是51，在給最后一項賦值之前，js會將前50項都置為 undefined，自然會影響效率。
一行代碼完成優化：

// let cache = []; let cache = {}; 復制代碼

生命不息，優化不止

優化是門學問，如果你還不肯善罷甘休的話，我也只能送你到這里了，畢竟本文的目的旨在幫你回憶起這么一道經典的題目（逃）。
如果某位數學大神看到了我這篇渣渣文，肯定會十分不屑的反手就是一個通項公式，emmmmm你開心就好。

最后

新年快樂 : )

總結

以上是生活随笔為你收集整理的五分钟重温斐波那契数列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。