两种Fibnacci递归求解对比

斐波那契数列

在我学C的时候,Fibnacci就是作为递归算法入门的经典案例。斐波那契数列是由列奥纳多•斐波那契通过兔子繁殖的例子提出的,对各个科学领域有非常重要的意义。

斐波那契数列:1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
如果设F(n)为该数列的第n项(n∈N*),那么这句话可以写成如下形式::F(n)=F(n-1)+F(n-2)
显然这是一个线性递推数列。

参见百科词条

让我们来看看它是怎么实现的。

普通递归求解

1
2
3
4
5
6
def fib(n):
if n == 0 or n == 1:
return 1
else:
return fib(n-1) + fib(n-2)
#return 1 if n==1 or n==0 else fib(n-1)+fib(n-2)
  • 首先我们定义了fib的函数fib,该递归使用降序,即从n到0或1,到达顶点时不再继续
  • 设置条件跳出递归循环,当n == 0 or 1
  • 如果不满足跳出条件(满足循环条件),则执行递归循环(fib(n-1) + fib(n-2))

我们来看一下执行的具体过程,以n = 5为例

1.fib(5)
2.fib(4)+fib(3)
3.(fib(3)+fib(2))+(fib(2)+fib(1))
4.((fib(2)+fib(1))+(fib(1)+showfib(0))+((fib(1)+fib(0))+fib(1)
5.(((fib(1)+fib(0))+fib(1))+(fib(1)+fib(0))+((fib(1)+fib(0))+fib(1)

从上面我们不难看出,当我们在对斐波那契数列递归求解时,同样的函数被调用了不只一次(fib(3)被调用了两次,fib(2)被调用了3次,fib(1)被调用了…

1
2
3
4
5
6
7
'''
5
4 3
3 2 2 1
2 1 1 0 1 0
1 0
'''

如果我们把fib函数的调用路径当做一个典型的二叉树,我们来看一下各函数的调用次数

函数 fib(5) fib(4) fib(3) fib(2) fib(1) fib(0)
次数 1 1 2 3 5 3(同2)

因为我们将1和0看作递归函数的顶点而合并,数量为fib(2)+fib(1)的数量,为8.我们不难看出各项运算次数为1,1,2,3,5,8,该数列即为fibnacci数列,而总的运算次数为fibnacci数列0-5各项之和

测试

我们这里来计算一下,fib(40)所用时间

1
2
3
localhost:optimization Jakob$ python3 slowfib.py 
fib[40]= 165580141
74.878676

计算fib(40)耗时74.87s.

使用动态规划

我们看了前面的计算方式后,发现过多的时间浪费在了重复的计算上。我们能不能找到一种方法更快速高效呢?我们来看下面的例子

1 1 2 3 5 8 13 21 ? 求出’?’所代表的fib(8)

非常简单,我们只需要13+21 = 34就求出来了。但是我们之前的方法在计算时并没有将计算的结果进行保留。所以这次我们要使用dict来将内容进行保留,方便后续运算参考

1
2
3
4
5
6
7
8
9
def fastfib(n,memo = {}):
if n == 0 or n == 1:
return 1
try:
return memo[n]
except KeyError:
result = fastfib(n-1,memo) + fastfib(n-2,memo)
memo[n]= result
return result

动态规划算法,是通过状态和状态转移来进行递推:当我们求得fib(3)使,我们的状态应该是fib1到3为已知,再求得fib4时,状态转移为fib1-4为已知

与之前的函数不同的是,我们这次添加了一个memo作为参考dict,而递归的结构是一样的:

  • 先判断n 是否为1 or 0
  • 如果不是,查找当前字典中是否有该项的值(是否已经被计算过),我们这里使用try..except来处理
  • 如果没有找到,计算出结果并添加到memo
  • 将memo中n对应的fib值作为结果返回

    1
    2
    3
    4
    5
    6
    7
    '''
    5
    4 3
    3 2 2 1
    2 1 1 0 1 0
    1 0
    '''

同样是二叉树,过程简单很多

  • fib(5)-> call fib(4) -> call fib(3) -> 2,1,从左边第一排开始向下
  • 结果逐级返回并添加入memo
  • 返回时只使用索引,无需深入计算
  • 得到fib(5)
  • 最后我们可以看出,我们只遍历了最左边一排节点5,4,3,2,1;以及右侧子节点(左数第二排,从下往上)0,1,2,3

测试

我们来看一下fastfib(40)需要多久

1
2
3
localhost:optimization Jakob$ python3 slowfastfib.py 
fib[40]= 165580141
0.000112000

耗时0.000112秒

fib(40)对比图