一、斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，具体如下：

第一个月：一对刚出生的小兔子
第二个月：小兔子变成大兔子并开始怀孕
第三个月：大兔子会生下一对小兔子，并且以后每个月都会生下一对小兔子。

如果每对兔子都经历这样的出生、成熟、生育的过程，并且兔子永远不死，那么兔子的总数是如何变化的？

在这里插入图片描述在写代码之前我们观察一下兔子增长的规律，每一个月的兔子其实就等于之前的成年兔子+在这个月长大的成年兔子+之前成年兔子生的宝宝兔子。

当前月的上个月兔子数 = 当前月所有的成年兔子
当前月的上上个月的兔子数 = 当前月中之前成年兔子生的兔宝宝的个数

使用公式表示如下：

 month    1 2 3 4 6 7  8  9 ...
 rabbits  1 1 2 3 5 8 21 34 ...

        | f(n-1) + f(n-2) n>=3
 f(n) = |
        |   1            n=1,2

二、斐波那契数列的实现

1. 使用迭代的方式实现

迭代：一种不断使用变量的旧值递推新值的过程。

我们使用迭代的写法如下：

int fib(int n){
    if(1 == n || 2 == n ) return 1;
    int a = 1; // a：表示上上一个月的兔子数
    int b = 1; // b：表示上一个月的兔子数
    for(int i=3; i<=n; ++i){
        int res = a+b; // 某个月的兔子数等于前两个月的兔子数之和
        a = b;  // 更新a
        b = res； // 更新b
    }
    return res;
}

2. 使用递归的方式实现

使用递归的方式就很简单了，代码如下：

int fib(int n){
    if(1 == n || 2 == n) return 1;
    return fib(n-1) + fib(n-2)
}

3. 比较以上两种实现方式

我们来运行一下递归的方式计算第45个月的兔子值
如下：
在这里插入图片描述
可以看到计算用了5s的时间，我们对比使用迭代的方式计算所用的时间：
只使用了0.001s，相比递归快了5000倍。

这是因为递归方法在计算过程中存在重复计算，如我们计算第5个月的兔子数：

     fib(5)
 =>  fib(4) + fib(3)
 =>  fib(3)+fib(2) + fib(2)+fib(1)

只是计算第五个月都会出现重复计算fib(3) fib(2)的情况，可想而知当计算的月份越大的时候重复计算的部分越多。

递归的方法的时间复杂度为O(2^n)
迭代的方法的时间复杂度为O(n)

三、优化递归实现——引入动态规划

这种由于重复计算的原因使得递归遍满可以使用动态规划中的备忘录法对其进行改进，其实就是将我们在递归过程中计算得到的某个月的值存在数组中，这样当我们需要使用某个月的值时就不需要重复计算，直接在数组中进行读取就可以。

具体代码如下：

int _fib(int* arr, int n){
    for(int i=3; i<n+1; ++i){
         if(arr[i] = 0){
             arr[i] = _fib(arr, i-1) +_fib(arr, i-2);
         }
    }
    return arr[n];
}
int fib(int n){
    if(1 == n || 2 == n) return 1;
    int arr[n+1];
    arr[1] = arr[2] = 1;
    for(int i=0; i<n+1; ++i){
        arr[i] = 0;
    }
    return _fib(arr, n-1) + _fib(arr, n-2);
}