递归式 的Fibonacci
假如兔子在出生两个月后就有繁殖能力，一对兔子每个月能生出一对小兔来，如果所有兔子都不会死，那么12个月后一共有多少对兔子？
调用次数的似乎比问题规模的平方增长的还要快，具体代码如下：
1 def fib(n): 2 if n < 3: 3 return 1 4 else: 5 return fib(n-1) - fib(n-2)
fib（4）需要4次递归调用，fib（6）需要14次递归调用
如果调用树是完全平衡的，最底部的两层都应该完全填满，参数为6的调用，会产生2+4+8+16 = 30次的递归调用，每个填满的层级上的调用次数都是上一个层级调用总数的两倍，因此完全平衡树的递归调用次数通常是2^n+1 - 2，这显然是指数级的O(n^k)的算法
尽管递归fib函数的调用数的地步并不是完全填满的，但是参数越来越多，足够接近一个完全平衡树，递归Fib的常数k接近1.63
指数算法通常只对较小的问题规模才符合实际
将Fibonacci转换为线性算法
通过将递归算法转换为基于循环的版本，降低其运行时间复杂度，虽然有时候可以删除递归，但不是总能减低其运行时间复杂度
1 def fib(n): 2 sum = 1 3 first = 1 4 second = 1 5 count = 3 6 while count <= n: 7 sum = first + second 8 first = second 9 second = first + sum 10 count += 1 11 return sum 12 13 14 print(fib(10))