一分钟学算法-递归-斐波那契数列递归解法及优化

一分钟学一个算法题目。

今天我们要学习的是用递归算法求解斐波那契数列。

首先我们要知道什么是斐波那契数列。

斐波那契数列，又称黄金分割数列，是一个经典的数学数列，其特点是第一项，第二项为1，后面每个数字都是前两个数字之和。推导过程如视频所示，非常非常简单。

知道了斐波那契数列的定义后，我们将其代入到递归问题的分析当中。

首先确定边界条件，就是第一项和第二项为1，接着确定递归关系，后一项等于前两项的和。确定了上面这些关系，我们就可以写出下面的代码了。

def fib(x):# 边界条件if x==1 or x==2: return 1# 递归关系return fib(x-2)+fib(x-1)print(fib(1))
print(fib(2))
print(fib(3))
print(fib(4))
print(fib(5))
print(fib(6))

没错，去掉注释和空行后只有三行代码，简洁精炼是递归问题的共性，你学习过肯定深有体会。下面我们稍微解读下代码，这是一个求解斐波那契数列第n项数字的函数，函数名为fib，接受一个参数n。
如果n等于1或者2，那么就返回1，否则就返回fib(n-2)与fib(n-1)的和，怎么样，脑子转过来弯了吗？没错，就是这么简单。我们来尝试运行使用函数检验一下正确性，发现都输出了正确结果。

但是这个函数还有很大的优化空间，在哪里呢？没错，递归算法让我们使用简洁的代码解决复杂的问题。但他的时间复杂度很高，一不小心没做好边界与转换关系判断就会导致无限循环或者栈溢出。

我们以此题为例，假如我们要求解斐波那契数列的第一百项数字，那麽我们会得到这张调用关系图，同一项会被重复计算非常非常多次。所以你运行此函数可能会导致很长时间都计算不出结果。

那么，我们该如何优化呢？
我们该如何避免重复计算某一项的值呢？

我们可以在计算出每一项的时候，把计算结果存到一个字典里。这样我们在每次计算前先去字典中寻找这一项，如果有值，那么直接拿出来使用，如果没有，再计算它。

这样的话我们就可以保证每一项仅被计算一次。运行时间也将会大大缩短。按照以上思路我们对代码进行如下变化。

def fib(n):# 边界条件if n==1 or n==2: return 1if hash.get(n,0):return hash.get(n)# 递归关系ans=fib(n-2)+fib(n-1)hash[ans]=ansreturn anshash={}

在代码中我们增加了以下变化：
每次计算某一项时先去集合中查询，如果已经计算过，那么直接返回值，如果没有，则计算，并且在返回值之前先在集合中记录一下。

这样代码的算法复杂度已经优化了很多了，没有优化版本求解第70项都非常费力，现在优化后已经可以轻松算出第100项了。但要想算出第一百项还是需要很久时间。

因为其中还存在大量的分支判断。

而且此解法还远远不是最优解法，关注up主，我们下集就来讲讲更快的方法。