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

今日分享：群众从来没有渴望过真理，面对那些不合口味的证据，他们会拂袖而去，假如谬论对他们有诱惑力，他们更愿意崇拜谬论。凡是能向他们供应幻觉的，也可以很容易地成为他们的主人，凡是让他们幻灭的，都会成为他们的牺牲品。

前言

假如面试官让你编写求斐波那契数列的代码时，是不是心中暗喜?不就是递归么，早就会了。如果真这么想，那就危险了。

递归求斐波那契数列

递归，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。
斐波那契数列的计算表达式很简单：

1F(n) = n; n = 0,1
2F(n) = F(n-1) + F(n-2),n >= 2;

因此，我们能很快根据表达式写出递归版的代码：

 1/*fibo.c*/
 2#include <stdio.h>
 3#include <stdlib.h>
 4/*求斐波那契数列递归版*/
 5unsigned long fibo(unsigned long int n)
 6{
 7    if(n <= 1)
 8        return n;
 9    else 
10        return fibo(n-1) + fibo(n-2);
11}
12int main(int argc,char *argv[])
13{
14    if(1 >= argc)
15    {
16       printf("usage:./fibo num\n");
17       return -1;
18    }
19    unsigned long  n = atoi(argv[1]);
20    unsigned long  fiboNum = fibo(n);
21    printf("the %lu result is %lu\n",n,fiboNum);
22    return 0;
23}

关键代码为3~9行。简洁明了，一气呵成。
编译：

1gcc -o fibo fibo.c

运行计算第5个斐波那契数：

1$ time ./fibo 5
2the 5 result is 5
3
4real    0m0.001s
5user    0m0.001s
6sys    0m0.000s

看起来并没有什么不妥，运行时间也很短。
继续计算第50个斐波那契数列：

1$ time ./fibo 50
2the 50 result is 12586269025
3
4real    1m41.655s
5user    1m41.524s
6sys    0m0.076s

计算第50个斐波那契数的时候，竟然花了将近两分钟！而且如果你在fibo函数中定义一些局部变量，时间将会变得更长！

递归分析

为什么计算第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中，我们可以通过下面的命令查看栈空间的软限制：

1$ ulimit -s
28192

可以看到，默认栈空间大小只有8M。一般来说，8M的栈空间对于一般程序完全足够。如果8M的栈空间不够使用，那么就需要重新审视你的代码设计了。

迭代解法

既然递归法不够优雅，我们换一种方法。如果不用计算机计算，让你去算第n个斐波那契数，你会怎么做呢？我想最简单直接的方法应该是：知道第一个和第二个后，计算第三个；知道第二个和第三个后，计算第四个，以此类推。最终可以得到我们需要的结果。这种思路，没有冗余的计算。基于这个思路，我们的C语言实现如下：

 1/*fibo1.c*/
 2#include <stdio.h>
 3#include <stdlib.h>
 4/*求斐波那契数列迭代版*/
 5unsigned long  fibo(unsigned long  n)
 6{
 7    unsigned long  preVal = 1;
 8    unsigned long  prePreVal = 0;
 9    if(n <= 2)
10        return n;
11    unsigned long  loop = 1;
12    unsigned long  returnVal = 0;
13    while(loop < n)
14    {
15        returnVal = preVal +prePreVal;
16        /*更新记录结果*/
17        prePreVal = preVal;
18        preVal = returnVal;
19        loop++;
20    }
21    return returnVal;
22}
23/**main函数部分与fibo.c相同，这里省略*/

编译并计算第50个斐波那契数：

1$ gcc -o fibo1 fibo1.c
2$ time ./fibo1 50
3the 50 result is 12586269025
4
5real    0m0.002s
6user    0m0.001s
7sys    0m0.002s

可以看到，计算第50个斐波那契数只需要0.002s！时间复杂度为O(n)。

尾递归解法

同样的思路，但是采用尾递归的方法来计算。要计算第n个斐波那契数，我们可以先计算第一个，第二个，如果未达到n，则继续递归计算，尾递归C语言实现如下：

 1/*fibo2.c*/
 2#include <stdio.h>
 3#include <stdlib.h>
 4/*求斐波那契数列尾递归版*/
 5unsigned long fiboProcess(unsigned long n,unsigned long  prePreVal,unsigned long  preVal,unsigned long begin)
 6{
 7    /*如果已经计算到我们需要计算的，则返回*/
 8    if(n == begin)
 9        return preVal+prePreVal;
10    else
11    {
12        begin++;
13        return fiboProcess(n,preVal,prePreVal+preVal,begin);
14    }
15}
16
17unsigned long  fibo(unsigned long  n)
18{
19    if(n <= 1)
20        return n;
21    else 
22        return fiboProcess(n,0,1,2);
23}
24
25/**main函数部分与fibo.c相同，这里省略*/

效率如何呢？

1$ gcc -o fibo2 fibo2.c
2$ time ./fibo2 50
3the 50 result is 12586269025
4
5real    0m0.002s
6user    0m0.001s
7sys    0m0.002s

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

其他解法

其他两种时间复杂度为O(logn)的矩阵解法以及O(1)的通项表达式解法本文不介绍。欢迎留言补充。

总结

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

• 实现简单

• 可读性好

缺点：

• 递归调用，占用空间大

• 递归太深，易发生栈溢出

• 可能存在重复计算

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