递归解法
F(n) = n; n = 0,1
F(n) = F(n-1) + F(n-2),n >= 2;
斐波那契数列的推导式如上，相当简单，所以很容易就能写出递归的解法。
import time
from functools import wraps
def print_func_time(function):
@wraps(function)
def func_time(*args, **kwargs):
t0 = time.perf_counter()
result = function(*args, **kwargs)
t1 = time.perf_counter()
print("Total running time: %s s" % (str(t1 - t0)))
return result
return func_time
def fiBo(n):
if n <= 1:
return n
else:
return fiBo(n - 1) + fiBo(n - 2)
@print_func_time
def solution(n):
print(fiBo(n))
# 0 1 1 2 3 5 8
if __name__ == '__main__':
solution(40)
out：
102334155 Total running time: 41.485671385 s
显然，才 40，时间效率就很低下了。
这是为什么呢？
当我们计算 5 的时候，会进行下面这样的计算：
|--F(1)
|--F(2)|
|--F(3)| |--F(0)
| |
|--F(4)| |--F(1)
| |
| | |--F(1)
| |--F(2)|
| |--F(0)
F(5)|
| |--F(1)
| |--F(2)|
| | |--F(0)
|--F(3)|
|
|--F(1)
为了计算 fibo(5)，需要计算 fibo(3)，fibo(4)；而为了计算 fibo(4)，需要计算 fibo(2)，fibo(3)……最终为了得到 fibo(5)的结果，fibo(0)被计算了 3 次，fibo(1)被计算了 5 次，fibo(2)被计算了 2 次。可以看到，它的计算次数几乎是指数级的
因此，虽然递归算法简洁，但是在这个问题中，它的时间复杂度却是难以接受的。除此之外，递归函数调用的越来越深，它们在不断入栈却迟迟不出栈，空间需求越来越大，虽然访问速度高，但大小是有限的，最终可能导致栈溢出。 在 linux 中，我们可以通过下面的命令查看栈空间的软限制：
$ ulimit -s
8192
可以看到，默认栈空间大小只有 8M。一般来说，8M 的栈空间对于一般程序完全足够。如果 8M 的栈空间不够使用，那么就需要重新审视你的代码设计了。
改进递归
既然我们知道最初版本的递归存在大量的重复计算，那么我们完全可以考虑将已经计算的值保存起来，从而避免重复计算，该版本代码实现如下：
def fiBo(n, lst):
if n < 2:
return n
else:
lst[n] = fiBo(n-1, lst) + lst[n-2]
return lst[n]
@print_func_time
def solution(n, lst):
print(fiBo(n, lst))
# 0 1 1 2 3 5 8
if __name__ == '__main__':
arr = [0]+[1]*40
solution(40, arr)
out：
102334155 Total running time: 2.6667000000035745e-05 s
显然可见其效率还是不错的，时间复杂度为 O(n)。
但是特别注意的是，这种改进版的递归，虽然避免了重复计算，但是调用链仍然比较长。
迭代解法
显然，让你来算，你肯定不会说我先算 40，然后发现要算 39。
你肯定是算：
0+1=1
1+1=2
2+1=3
3+5=5
5+3=8
……
我们是正向计算的，而且是不断向后计算的。
理解到区别了没。
那么，我们是否也可以这样进行计算呢，显然，是可以的。
def fiBo(n):
n = n+1
pre1 = 0
pre2 = 1
if n < 2:
return n
loop = 1
ret = 0
while loop < n:
ret = pre1 + pre2
pre2 = pre1
pre1 = ret
loop += 1
# 可以使用Python的语法糖代替上面的循环体
# tmp = pre1 + pre2
# ret, pre2, pre1, loop = tmp, pre1, tmp, loop + 1
return ret
@print_func_time
def solution(n):
print(fiBo(n))
# 0 1 1 2 3 5 8
if __name__ == '__main__':
solution(40)
out：
102334155
Total running time: 2.0102999999993543e-05 s
时间复杂度为 O(n)。
尾递归解法
同样的思路，但是采用尾递归的方法来计算。
要计算第 n 个斐波那契数，我们可以先计算第一个，第二个，如果未达到 n，则继续递归计算。
def fiBoProcess(n, pre1, pre2, begin):
if n == begin:
return pre1 + pre2
else:
begin += 1
return fiBoProcess(n, pre2, pre1 + pre2, begin)
def fiBo(n):
if n < 2:
return n
else:
return fiBoProcess(n, 0, 1, 2)
@print_func_time
def solution(n):
print(fiBo(n))
# 0 1 1 2 3 5 8
if __name__ == '__main__':
solution(40)
out：
102334155 Total running time: 2.338399999995966e-05 s
可见，其效率并不逊于迭代法。尾递归在函数返回之前的最后一个操作仍然是递归调用。尾递归的好处是，进入下一个函数之前，已经获得了当前函数的结果，因此不需要保留当前函数的环境，内存占用自然也是比最开始提到的递归要小。时间复杂度为 O(n)。