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

这篇具有很好参考价值的文章主要介绍了一分钟学算法-递归-斐波那契数列递归解法及优化。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一分钟学算法-递归-斐波那契数列递归解法及优化,Python,算法详解,算法,哈希算法

一分钟学一个算法题目。

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

视频教程链接：https://www.bilibili.com/video/BV1Wu4y1i7JJ/

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

斐波那契数列，又称黄金分割数列，是一个经典的数学数列，其特点是第一项，第二项为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 1

    if hash.get(n,0):
        return hash.get(n)

    # 递归关系
    ans=fib(n-2)+fib(n-1)
    hash[ans]=ans
    return ans

hash={}