斐波那契數(shù)列的遞歸方法眾所周知，但是遞歸也不是一個(gè)高效的解決方法。
從下邊的調(diào)用圖可以看出來(lái)：

其中，對(duì)于1和2的計(jì)算重復(fù)了多次。
因此如果對(duì)數(shù)列中已經(jīng)計(jì)算過(guò)的數(shù)字進(jìn)行存儲(chǔ)這樣就可以只計(jì)算一次每個(gè)數(shù)值，達(dá)到高效的目的，計(jì)算時(shí)間也相對(duì)減少了。

1 known = {0:0,1:1}
2 
3 def fibonacci(n):
4     if n in known:
5         return known[n]
6 
7     res = fibonacci(n-1)+fibonacci(n-2)
8     known[n] = res
9     return res

代碼如上，把計(jì)算過(guò)的數(shù)值添加到一個(gè)字典里，就可以避免重復(fù)計(jì)算。
注：字典的值可以使用列表，但是鍵不可以。但是為了解決這個(gè)問(wèn)題，鍵是可以使用元組的，以后遇到再解釋。
另外，開(kāi)始我也有點(diǎn)疑慮，為什么known不是一個(gè)全局變量但是卻能在函數(shù)里邊修改和調(diào)用，后來(lái)知道了在python中可以修改的變量是不必再次聲明全局的。而如果是個(gè)元組或者是個(gè)單獨(dú)的str或者int變量想在函數(shù)這個(gè)局部里邊使用就需要聲明全局，否則就是重新構(gòu)造了一個(gè)變量，而不是對(duì)原先的進(jìn)行修改。