3.斐波那契数列的高效方法

斐波那契数列的递归方法众所周知，但是递归也不是一个高效的解决方法。
从下边的调用图可以看出来：

其中，对于1和2的计算重复了多次。
因此如果对数列中已经计算过的数字进行存储这样就可以只计算一次每个数值，达到高效的目的，计算时间也相对减少了。

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

代码如上，把计算过的数值添加到一个字典里，就可以避免重复计算。
注：字典的值可以使用列表，但是键不可以。但是为了解决这个问题，键是可以使用元组的，以后遇到再解释。
另外，开始我也有点疑虑，为什么known不是一个全局变量但是却能在函数里边修改和调用，后来知道了在python中可以修改的变量是不必再次声明全局的。而如果是个元组或者是个单独的str或者int变量想在函数这个局部里边使用就需要声明全局，否则就是重新构造了一个变量，而不是对原先的进行修改。