Question

斐波那契数列递归算法是什么？

Answer 1

斐波那契数列递归算法是斐波那契数列的一种算法，又称为黄金分割数列，其算法规律为F(n)=F(n-1)+F(n-2)。

由于是以兔子的繁殖为例子引入的，因此也叫“兔子数列”。它指的是这样一个数列：0、1、1、2、3、5、8、13……，从这组数可以很明显看出这样一个规律：从第三个数开始，后边一个数一定是在其之前两个数的和。

可以用以下两种非递归算法来实现：

1、时间复杂度为O(N)，空间复杂度为O(N)：

创建一个数组，每次将前两个数相加后直接赋给后一个数。这样的话，有N个数就创建一个包含N个数的一维数组，所以空间复杂度为O(N)；由于只需从头向尾遍历一边，时间复杂度为O(N)。

2、时间复杂度为O(N)，空间复杂度为O(1)：

借助两个变量 first 和 second ，每次将 first 和 second 相加后赋给 third ，再将 second 赋给 first ，third 赋给 second，如此循环。