面试官问你斐波那契数列的时候不要高兴得太早

效率如何呢？

$ gcc -o fibo2 fibo2.c
$ time ./fibo2 50
the 50 result is 12586269025

real	0m0.002s
user	0m0.001s
sys	0m0.002s

可见，其效率并不逊于迭代法。尾递归在函数返回之前的最后一个操作仍然是递归调用。尾递归的好处是，进入下一个函数之前，已经获得了当前函数的结果，因此不需要保留当前函数的环境，内存占用自然也是比最开始提到的递归要小。时间复杂度为O(n)。

这是一种高效的解法，需要推导，对此不感兴趣的可直接看最终推导结果。下面的式子成立是显而易见的，不多做解释。
an={an2a⋅an2,n为偶数a⋅an2a⋅an2,n为奇数 a^n= begin{cases} a^{n over 2} acdot a^{n over 2}, & text {n为偶数} \ acdot a^{n over 2} acdot a^{n over 2}, & text{n为奇数} end{cases} an={a2n​a⋅a2n​,a⋅a2n​a⋅a2n​,​n为偶数n为奇数​

如果a为矩阵，等式同样成立，后面我们会用到它。
假设有矩阵2*2矩阵A，满足下面的等式：

A∗[f(n−1)f(n−2)]=[f(n)f(n−1)]=[f(n−1)+f(n−2)f(n−1)] A * begin{bmatrix} f(n-1) \ f(n-2)end{bmatrix} = begin{bmatrix} f(n) \ f(n-1)end{bmatrix} = begin{bmatrix} f(n-1)+f(n-2) \ f(n-1)end{bmatrix} A∗[f(n−1)f(n−2)​]=[f(n)f(n−1)​]=[f(n−1)+f(n−2)f(n−1)​]

可以得到矩阵A：
A=[1110] A = begin{bmatrix} 1 & 1 \ 1 & 0 \ end{bmatrix}A=[11​10​]

因此也就可以得到下面的矩阵等式：
[1110]∗[f(n−1)f(n−2)]=[f(n)f(n−1)] begin{bmatrix} 1 & 1 \ 1 & 0 \ end{bmatrix} * begin{bmatrix} f(n-1) \ f(n-2)end{bmatrix} = begin{bmatrix} f(n) \ f(n-1)end{bmatrix} [11​10​]∗[f(n−1)f(n−2)​]=[f(n)f(n−1)​]

再进行变换如下：

[1110]∗[1110]∗[f(n−2)f(n−3)]=[f(n)f(n−1)] begin{bmatrix} 1 & 1 \ 1 & 0 \ end{bmatrix} *begin{bmatrix} 1 & 1 \ 1 & 0 \ end{bmatrix} * begin{bmatrix} f(n-2) \ f(n-3)end{bmatrix} = begin{bmatrix} f(n) \ f(n-1)end{bmatrix} [11​10​]∗[11​10​]∗[f(n−2)f(n−3)​]=[f(n)f(n−1)​]

以此类推，得到：
[1110]n−1∗[f(1)f(0)]=[f(n)f(n−1)] begin{bmatrix} 1 & 1 \ 1 & 0 \ end{bmatrix} ^{n-1} * begin{bmatrix} f(1) \ f(0)end{bmatrix} = begin{bmatrix} f(n) \ f(n-1)end{bmatrix} [11​10​]n−1∗[f(1)f(0)​]=[f(n)f(n−1)​]

实际上f(n)就是矩阵$ A^{n-1} KaTeX parse error: Expected 'EOF', got '中' at position 1: 中̲的A[0][0],或者是矩阵 A^{n} $中的A[0][1]。

那么现在的问题就归结为，如何求解AnA^nAn，其中A为2*2的矩阵。根据我们最开始的公式，很容易就有思路，代码实现如下：

#include 
#include 
#include 
#define MAX_COL 2
#define MAX_ROW 2
typedef unsigned long MatrixType;

int matrixDot(MatrixType A[MAX_ROW][MAX_COL],MatrixType B[MAX_ROW][MAX_COL],MatrixType C[MAX_ROW][MAX_COL])
{
   
    MatrixType tempMa[MAX_ROW][MAX_COL] ;
    memset(tempMa,0,sizeof(tempMa));
    
    tempMa[0][0] = A[0][0] * B[0][0] + A[0][1] * B [1][0];
    tempMa[0][1] = A[0][0] * B[0][1] + A[0][1] * B [1][1];
    tempMa[1][0] = A[1][0] * B[0][0] + A[1][1] * B [1][0];
    tempMa[1][1] = A[1][0] * B[0][1] + A[1][1] * B [1][1];
    memcpy(C,tempMa,sizeof(tempMa));
   
    return 0;
}
MatrixType fibo(int n){
    if(n <= 1)
 return n;
    MatrixType result[][MAX_COL] = {1,0,0,1};
    MatrixType A[][2] = {1,1,1,0};
    while (n > 0) 
    {
 
 if (n&1) 
 {
     matrixDot(result,A,result);

 }
 n /= 2;
 matrixDot(A,A,A);
    }
    return result[0][1];
}

该算法的关键部分在于对AnA^nAn的计算,它利用了我们开始提到的等式，对奇数和偶数分别处理。假设n为9，初始矩阵为INIT则计算过程如下：

• 9为奇数，则计算INIT*A，随后A变为A*A，n变为9/2，即为4
• 4为偶数，则结果仍为INIT*A，随后A变为(A2)∗(A2)=A4(A^2)*(A^2)=A^4(A2)∗(A2)=A4，n变为4/2，即2
• 2为偶数，则结果仍未INIT*A,随后变A变为 (A4)∗(A4)=A8(A^4)*(A^4)=A^8(A4)∗(A4)=A8,n变为2/2，即1
• 1为奇数，则结果为INIT*(A^8)*A

可以看到，计算次数类似与二分查找次数，其时间复杂度为O(logn)。
运行试试看：

$ gcc -o fibo3 fibo3.c
$ time ./fibo3 50
the 50 result is 12586269025

real	0m0.002s
user	0m0.002s
sys	0m0.000s

斐波那契数列的通项公式为：
f(n)=(1+52)n−(1−52)n5f(n) = frac{({frac{1+sqrt5}{2}})^n-({frac{1-sqrt5}{2}})^n}{sqrt5}f(n)=5​(21+5​​)n−(21−5​​)n​
关于通项公式的求解，可以当成一道高考数列大题，有兴趣的可以尝试一下（提示：两次构造等比数列）。C语言代码实现如下：

#include 
#include 
#include 
unsigned long fibo(unsigned long n)
{
    if(n <=1 )
 return n;
    return (unsigned long)((pow((1+sqrt(5))/2,n)-pow((1-sqrt(5))/2,n))/sqrt(5));
}

来看一下效率：

$ gcc -o fibo4 fibo4.c -lm
$ time ./fibo4
the 50 result is 12586269025

real	0m0.002s
user	0m0.002s
sys	0m0.000s

计算第50个，速度还不错。

关于斐波那契数列在实际中很常见，数学上也有很多奇特的性质，有兴趣的可在百科中查看。

总结一下递归的优缺点：
优点：

• 实现简单
• 可读性好

缺点：

• 递归调用，占用空间大
• 递归太深，易发生栈溢出
• 可能存在重复计算

可以看到，对于求斐波那契数列的问题，使用一般的递归并不是一种很好的解法。
所以，当你使用递归方式实现一个功能之前，考虑一下使用递归带来的好处是否抵得上它的代价。