1、斐波那契数列

最先研究这个数列的人是意大利人斐波那契，Leonardo Fibonacci，他在描述兔子生长的数目时用上了这数列:

• 第一个月初有一对刚诞生的兔子；
• 第二个月还是只有这一对；
• 第三个月初它们可以生育；
• 以后每月每对可生育的兔子会诞生下一对新兔子；
• 兔子永不死去。

每个月兔子的总对数，就是这样一个序列：

1, 1, 2, 3, 5, 8, 13, 21...

这个序列从第三项开始，每一项都等于前两项之和。

在数学上，斐波那契数列是以递归的方法来定义：

F(1) = 1

F(2) = 1

F(n) = F(n-1) + F(n-2) (n≥3)

2、代码实现

2.1、递归实现

根据斐波那契数列的数学定义，用递归可以很快实现，且代码简洁易懂。

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

递归实现虽然简洁，但却有许多重复计算，当 n 的值非常大时，重复计算的次数就会急剧增加，事实上该算法的时间复杂度随着 n 值的增加呈指数增长，其时间复杂度却为 O(2^n)。

有没有时间复杂度较低的算法呢？

2.2、循环实现

F(n) = F(n-1) + F(n-2) (n≥3)

采用递归的方式实现，有许多重复计算，这些重复计算其实是不必要的。观察斐波那契数列的数学定义，F(n) 的值只与前两项相关，对于任意一个 n 值，只要记住这两个值，并不断更新，就可以避免重复计算。

int fibo(int n) {
    if ((n == 1) || (n == 2)) {
        return 1;
    }
  
    int prev = 1;
    int curr = 1;
  
    for (int i = 3; i <= n; i++) {
        int sum = prev + curr;
        prev = curr;
        curr = sum;
    }
  
    return curr;
}

采用循环的方式，时间复杂度降为 O(n)。