斐波那契數(shù)列是數(shù)學(xué)領(lǐng)域內(nèi)一個非常經(jīng)典的算法問題（算法渣寫下這句話的時候都在瑟瑟發(fā)抖），今天就用五分鐘的篇幅來淺析一下這個問題。

什么是斐波那契數(shù)列？

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

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

采用遞歸實現(xiàn)

有編程經(jīng)驗的你一定會想到遞歸。好的開始是成功的一半，如果你能想到遞歸，那么離成功已經(jīng)不遠(yuǎn)了。
不難看出，數(shù)列的遞推規(guī)律可以總結(jié)為：

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

okay，挽起袖子開擼

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

乍一看，完美。
不過這個時候，但凡是個稍微有點追求的 Developer 都會說：“大兄弟你這么搞不是最優(yōu)解呀，數(shù)字稍微大一點就炒雞慢了。”

有緩存的 Fibonacci

雖然人艱不拆，但是優(yōu)化還是要做的。
我不禁想到了前端性能優(yōu)化里面最常見且好用的一條：緩存。大概的思路就是，將新算出來的值保存起來以便下一次使用。
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);}} })(); 復(fù)制代碼

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

// let cache = []; let cache = {}; 復(fù)制代碼

生命不息，優(yōu)化不止

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

最后

新年快樂 : )

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。