怎么引入斐波那契数列递归算法（7种方式实现斐波那契数）

昨天发了一篇斐波那契数列的递归和非递归求法，结果大家纷纷询问其他方法可不可以，询问哪种方法更靠谱，我滴个神，其他方法当然可以，条条大路通罗马嘛，况且代码这个东西，本就灵活多变。

那今天，我干脆直接把我所能想到的实现斐波那契数列的方法和代码都贴在这，方便大家参考~~~

还有，千万别问我这是不是小学生学的东西了，捂脸。这真的是编程入门级的算法，我遇到很多小学生编程超级厉害的hhh。

好了，闲言少叙，开始正题：

在学校里学习递归的时候，老师就喜欢举斐波那契这个例子，看！多简洁清晰。其实这个例子是非常不适合作为递归举例的，原因就是效率太慢，除了最后一个数，每个数都被算了一遍又一遍，时间复杂度差不多是5n^2/3。

昨天有说过，递归实现，而且还讨论了它的时间复杂度，那一长串表达式，如果能理解更好，不理解也没关系，记得它的时间复杂度差不多是5n^2/3就好。

关键代码如下：

方法一递归Fib1

二：数组实现

昨天也有小伙伴问数组可不可以，当然可以！

用数组实现，其空间复杂度和时间复杂度都是0(n)，效率一般，比递归来得快。

代码如下：

方法二数组Fib2

三：vector<int>实现

vector是一个动态的序列容器，相当于一个size可变的数组。

相比于数组，vector会消耗更多的内存以有效的动态增长。而相比于其他动态序列容器(deques, lists and forward_lists)，vector能更快的索引元素(就像数组一样)，而且能相对高效的在尾部插入和删除元素。如果不是在尾部插入和删除元素，效率就没有这些容器高。

使用这种方法空间复杂度是0(n)，时间复杂度是0(1)。

代码如下：

方法三Fib3

四：queue<int>实现

队列比数组更适合实现斐波那契数列，时间复杂度和空间复杂度和vector<int>一样，但队列太适合这里了，f(n)=f(n-1) f(n-2)，f(n)只和f(n-1)和f(n-2)有关，前面的数就乖乖的出队列吧。

不过大部分初学者一开始是不会接触到队列的，讲编程的时候，也不会这么粗暴地直接就讲队列，所以一般来说，一开始大家不知道这种方法也是没有办法的，我这边列出来，大家参考一下，知道有这种方法就好。

代码如下：

Fib4 最合适的方式

五：迭代实现

迭代实现是最高效的，昨天有介绍了这个方法，不知道大家懂了没有，时间复杂度是0(n)，空间复杂度是0(1)。

代码如下：

Fib5 最简单的方式

六：矩阵实现

昨天好多小伙伴也都说，矩阵实现最好最优雅了，来来来，我们了解一下矩阵实现的原理。

矩阵（matrix）定义

一个m*n的矩阵是一个由m行n列元素排成的矩形阵列，矩阵里的元素可以是数字符号或者数学式。

一个最简单的矩阵长这样：

它是一个具体的数，并且结果等于ad-bc。

斐波那契数列矩阵

数斐波那契列的递推公式为：f(1)=1，f(2)=2，f(n)=f(n-1) f(n-2)(n>=3)

用矩阵表示为：

进一步，可以得出直接推导公式：

由于矩阵乘法满足结合律，在程序中可以事先给定矩阵的64，32，16，8，4，2，1次方，加快程序的执行时间。（有些题目需要取模运算，也可以事先进行一下）。

哎呀，到此打住吧，矩阵实现代码太长，就不截图放上来了，想要的同学可以私信我。

七：公式实现

原来斐波那契数列有公式啊，那老师干嘛不直接教我们公式呢，教我们公式，当然要告诉我们推导啊，这个推导过程，emmmmm，实在丧心病狂。

来看一眼这个公式：

斐波那契通项公式

而且利用公式的话，由于double类型的精度还不够，所以程序算出来的结果有误差，当然初期我们可能不care这个误差，但是计算机是一个严谨的学科，ennn，算了，不说大道理了。

代码如下：

Fib7

,