前言
假如面试官让你编写求斐波那契数列的代码时，是不是心中暗喜?不就是递归么，早就会了。如果真这么想，那就危险了。
递归求斐波那契数列
递归，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。
斐波那契数列的计算表达式很简单：
F(n) = n; n = 0,1
F(n) = F(n-1) + F(n-2),n >= 2;
因此，我们能很快根据表达式写出递归版的代码：
/*fibo.c*/
#include <stdio.h>
#include <stdlib.h>
/*求斐波那契数列递归版*/
unsigned long fibo(unsigned long int n)
{
if(n <= 1)
return n;
else
return fibo(n-1) + fibo(n-2);
}
int main(int argc,char *argv[])
{
if(1 >= argc)
{
printf("usage:./fibo num\n");
return -1;
}
unsigned long n = atoi(argv[1]);
unsigned long fiboNum = fibo(n);
printf("the %lu result is %lu\n",n,fiboNum);
return 0;
}
关键代码为3~9行。简洁明了，一气呵成。
编译：
gcc -o fibo fibo.c
运行计算第5个斐波那契数：
$ time ./fibo 5
the 5 result is 5
real 0m0.001s
user 0m0.001s
sys 0m0.000s
看起来并没有什么不妥，运行时间也很短。
继续计算第50个斐波那契数列：
$ time ./fibo 50
the 50 result is 12586269025
real 1m41.655s
user 1m41.524s
sys 0m0.076s
计算第50个斐波那契数的时候，竟然将近两多钟！
递归分析
为什么计算第50个的时候竟然需要1分多钟。我们仔细分析我们的递归算法，就会发现问题，当我们计算fibo(5)的时候，是下面这样的：
|--F(1)
|--F(2)|
|--F(3)| |--F(0)
| |
|--F(4)| |--F(1)
| |
| | |--F(1)
| |--F(2)|
| |--F(0)
F(5)|
| |--F(1)
| |--F(2)|
| | |--F(0)
|--F(3)|
|
|--F(1)
为了计算fibo(5)，需要计算fibo(3)，fibo(4)；而为了计算fibo(4)，需要计算fibo(2)，fibo(3)…最终为了得到fibo(5)的结果，fibo(0)被计算了3次，fibo(1)被计算了5次，fibo(2)被计算了2次。可以看到，它的计算次数几乎是指数级的！
因此，虽然递归算法简洁，但是在这个问题中，它的时间复杂度却是难以接受的。除此之外，递归函数调用的越来越深，它们在不断入栈却迟迟不出栈，空间需求越来越大，虽然访问速度高，但大小是有限的，最终可能导致栈溢出。
在linux中，我们可以通过下面的命令查看栈空间的软限制：
$ ulimit -s
8192
可以看到，默认栈空间大小只有8M。一般来说，8M的栈空间对于一般程序完全足够。如果8M的栈空间不够使用，那么就需要重新审视你的代码设计了。
递归改进版
既然我们知道最初版本的递归存在大量的重复计算，那么我们完全可以考虑将已经计算的值保存起来，从而避免重复计算，该版本代码实现如下：
/*fibo3.c*/
#include <stdio.h>
#include <stdlib.h>
/*求斐波那契数列，避免重复计算版本*/
unsigned long fiboProcess(unsigned long *array,unsigned long n)
{
if(n < 2)
return n;
else
{
/*递归保存值*/
array[n] = fiboProcess(array,n-1) + array[n-2];
return array[n];
}
}
unsigned long fibo(unsigned long n)
{
if(n <= 1)
return n;
unsigned long ret = 0;
/*申请数组用于保存已经计算过的内容*/
unsigned long *array = (unsigned long*)calloc(n+1,sizeof(unsigned long));
if(NULL == array)
{
return -1;
}
array[1] = 1;
ret = fiboProcess(array,n);
free(array);
array = NULL;
return ret;
}
/**main函数部分与fibo.c相同，这里省略*/
效率如何呢？
$ gcc -o fibo0 fibo3.c
$ time ./fibo0 50
the 50 result is 12586269025
real 0m0.002s
user 0m0.002s
sys 0m0.001s
可见其效率还是不错的，时间复杂度为O(n)。但是特别注意的是，这种改进版的递归，虽然避免了重复计算，但是调用链仍然比较长。
迭代解法
既然递归法不够优雅，我们换一种方法。如果不用计算机计算，让你去算第n个斐波那契数，你会怎么做呢？我想最简单直接的方法应该是：知道第一个和第二个后，计算第三个；知道第二个和第三个后，计算第四个，以此类推。最终可以得到我们需要的结果。这种思路，没有冗余的计算。基于这个思路，我们的C语言实现如下：
/*fibo1.c*/
#include <stdio.h>
#include <stdlib.h>
/*求斐波那契数列迭代版*/
unsigned long fibo(unsigned long n)
{
unsigned long preVal = 1;
unsigned long prePreVal = 0;
if(n <= 2)
return n;
unsigned long loop = 1;
unsigned long returnVal = 0;
while(loop < n)
{
returnVal = preVal +prePreVal;
/*更新记录结果*/
prePreVal = preVal;
preVal = returnVal;
loop++;
}
return returnVal;
}
/**main函数部分与fibo.c相同，这里省略*/
编译并计算第50个斐波那契数：
$ gcc -o fibo1 fibo1.c
$ time ./fibo1 50
the 50 result is 12586269025
real 0m0.002s
user 0m0.001s
sys 0m0.002s
可以看到，计算第50个斐波那契数只需要0.002s！时间复杂度为O(n)。
尾递归解法
同样的思路，但是采用尾递归的方法来计算。要计算第n个斐波那契数，我们可以先计算第一个，第二个，如果未达到n，则继续递归计算，尾递归C语言实现如下：
/*fibo2.c*/
#include <stdio.h>
#include <stdlib.h>
/*求斐波那契数列尾递归版*/
unsigned long fiboProcess(unsigned long n,unsigned long prePreVal,unsigned long preVal,unsigned long begin)
{
/*如果已经计算到我们需要计算的，则返回*/
if(n == begin)
return preVal+prePreVal;
else
{
begin++;
return fiboProcess(n,preVal,prePreVal+preVal,begin);
}
}
unsigned long fibo(unsigned long n)
{
if(n <= 1)
return n;
else
return fiboProcess(n,0,1,2);
}
/**main函数部分与fibo.c相同，这里省略*/
效率如何呢？
$ 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} a\cdot a^{n \over 2}, & \text {n为偶数} \\ a\cdot a^{n \over 2} a\cdot a^{n \over 2}, & \text{n为奇数} \end{cases} an={a2na⋅a2n,a⋅a2na⋅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=[1110]
因此也就可以得到下面的矩阵等式：
[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} [1110]∗[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} [1110]∗[1110]∗[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} [1110]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的矩阵。根据我们最开始的公式，很容易就有思路，代码实现如下：
/*fibo3.c*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_COL 2
#define MAX_ROW 2
typedef unsigned long MatrixType;
/*计算2*2矩阵乘法，这里没有写成通用形式，有兴趣的可以自己实现通用矩阵乘法*/
int matrixDot(MatrixType A[MAX_ROW][MAX_COL],MatrixType B[MAX_ROW][MAX_COL],MatrixType C[MAX_ROW][MAX_COL])
{
/*C为返回结果，由于A可能和C相同，因此使用临时矩阵存储*/
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)
{
/*判断最后一位是否为1，即可知奇偶*/
if (n&1)
{
matrixDot(result,A,result);
}
n /= 2;
matrixDot(A,A,A);
}
return result[0][1];
}
/**main函数部分与fibo.c相同，这里省略*/
该算法的关键部分在于对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语言代码实现如下：
/*fibo4.c*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
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));
}
/**main函数部分与fibo.c相同，这里省略*/
来看一下效率：
$ gcc -o fibo4 fibo4.c -lm
$ time ./fibo4
the 50 result is 12586269025
real 0m0.002s
user 0m0.002s
sys 0m0.000s
计算第50个，速度还不错。
斐波那契数列应用
关于斐波那契数列在实际中很常见，数学上也有很多奇特的性质，有兴趣的可在百科中查看。
总结
总结一下递归的优缺点：
优点：
- 实现简单
- 可读性好
缺点：
- 递归调用，占用空间大
- 递归太深，易发生栈溢出
- 可能存在重复计算
可以看到，对于求斐波那契数列的问题，使用一般的递归并不是一种很好的解法。
所以，当你使用递归方式实现一个功能之前，考虑一下使用递归带来的好处是否抵得上它的代价。