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

r囧r小猫 2022-03-29 13:21 128阅读 0赞

--------------------

## 前言 ##

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

## 递归求斐波那契数列 ##

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

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)。

## 矩阵快速幂解法 ##

这是一种高效的解法，需要推导，对此不感兴趣的可直接看最终推导结果。下面的式子成立是显而易见的，不多做解释。![20190222182100159.png][]

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

![20190222182100496.png][]

可以得到矩阵A：![20190222182100334.png][]

因此也就可以得到下面的矩阵等式：![20190222182100331.png][]

再进行变换如下：

![20190222182100519.png][]

以此类推，得到：![20190222182100353.png][]

实际上f(n)就是矩阵![20190222182100331.png][]中的A\[0\]\[0\],或者是矩阵![20190222182100324.png][]中的A\[0\]\[1\]。

那么现在的问题就归结为，如何求解![20190222182100335.png][]，其中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相同，这里省略*/

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

*  9为奇数，则计算INIT\*A，随后A变为A\*A，n变为9/2，即为4
 *  4为偶数，则结果仍为INIT\*A，随后A变为![20190222182100493.png][]，n变为4/2，即2
 *  2为偶数，则结果仍未INIT\*A,随后变A变为 ![20190222182100477.png][],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

## 通项公式解法 ##

斐波那契数列的通项公式为：  
![20190222182100489.png][]  
关于通项公式的求解，可以当成一道高考数列大题，有兴趣的可以尝试一下（提示：两次构造等比数列）。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个，速度还不错。

## 列表法 ##

如果需要求解的斐波那契数列的第n个在有限范围内，那么完全可以将已知的斐波那契数列存储起来，在需要的时候读取即可，时间复杂度可以为O(1)。

## 斐波那契数列应用 ##

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

## 总结 ##

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

*  实现简单
 *  可读性好

缺点：

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

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

最新内容地址：[重新看递归][Link 1]

> 微信公众号【编程珠玑】：专注但不限于分享计算机编程基础，Linux，C语言，C++，算法，数据库等编程相关\[原创\]技术文章，号内包含大量经典电子书和视频学习资源。欢迎一起交流学习，一起修炼计算机“内功”，知其然，更知其所以然。

[20190222182100159.png]: /images/20220329/0e7accf6cb9745b6a43952dffb451dd8.png
[20190222182100496.png]: /images/20220329/2882aec6875a42619eb97645c38b9552.png
[20190222182100334.png]: /images/20220329/bfa4bb8ded054362ae3a08bae74fe7f6.png
[20190222182100331.png]: /images/20220329/d24ccce026fe4813afc146d6c6a6ede4.png
[20190222182100519.png]: /images/20220329/26929d4f26c94d8ba33a6f11801c2ebc.png
[20190222182100353.png]: /images/20220329/275fb33813834ed69fc0696a43e59425.png
[20190222182100324.png]: /images/20220329/4dec4378536e46f7989dc5e3571a6880.png
[20190222182100335.png]: /images/20220329/7be7ed1ce51f4010a4d7b3e00bf24bae.png
[20190222182100512.png]: /images/20220329/c255c7f518c044bf8f0b6725eabd1d27.png
[20190222182100493.png]: /images/20220329/06921486291d4aec96023b36bebd70be.png
[20190222182100477.png]: /images/20220329/6378cc8152f348c19683628ae93271c5.png
[20190222182100489.png]: /images/20220329/127d5f79cf3e4e15a2daad70db7fa23e.png
[Link 1]: https://www.yanbinghu.com/2019/01/07/16863.html