求职干货：再也不怕面试官问斐波那契数列了！

原标题：求职干货：再也不怕面试官问斐波那契数列了！

??

作者 | 守望

责编 | 胡巍巍

前言

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

递归解法

递归，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。

斐波那契数列的计算表达式很简单：

F(n) = n; n = 0,1

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

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

/*fibo.c*/

#include<stdio.h>

#include<stdlib.h>

/*求斐波那契数列递归版*/

unsignedlongfibo(unsignedlongintn)

{

if(n <= 1)

returnn;

else

returnfibo(n-1) + fibo(n-2);

}

intmain(intargc,char*argv[])

{

if(1>= argc)

{

printf("usage:./fibo numn");

return-1;

}

unsignedlongn = atoi(argv[1]);

unsignedlongfiboNum = fibo(n);

printf("the %lu result is %lun",n,fiboNum);

return0;

}

关键代码只有4行。简洁明了，一气呵成。

编译：

gcc-ofibofibo.c

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

$ time ./fibo 5

the 5result is 5

real0m0.001s

user 0m0.001s

sys 0m0.000s

看起来并没有什么不妥，运行时间也很短。

继续计算第50个斐波那契数列：

$ time ./fibo 50

the 50result is 12586269025

real1m41.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的栈空间不够使用，那么就需要重新审视你的代码设计了。

递归改进版

既然我们知道最初版本的递归存在大量的重复计算，那么我们完全可以考虑将已经计算的值保存起来，从而避免重复计算，该版本代码实现如下：

/*fibo0.c*/

#include<stdio.h>

#include<stdlib.h>

/*求斐波那契数列，避免重复计算版本*/

unsignedlongfiboProcess(unsignedlong*array,unsignedlongn)

{

if(n < 2)

returnn;

else

{

/*递归保存值*/

array[n] = fiboProcess(array,n-1) + array[n-2];

returnarray[n];

}

}

unsignedlongfibo(unsignedlongn)

{

if(n <= 1)

returnn;

unsignedlongret = 0;

/*申请数组用于保存已经计算过的内容*/

unsignedlong*array= (unsignedlong*)calloc(n+1,sizeof(unsignedlong));

if(NULL== array)

{

return-1;

}

array[1] = 1;

ret = fiboProcess(array,n);

free(array);

array= NULL;

returnret;

}

/**main函数部分与fibo.c相同，这里省略*/

效率如何呢？

$ gcc -o fibo0 fibo0.c

$ time ./fibo0 50

the 50result is 12586269025

real0m0.002s

user 0m0.000s

sys 0m0.002s

可见其效率还是不错的，时间复杂度为O(n)。

但是特别注意的是，这种改进版的递归，虽然避免了重复计算，但是调用链仍然比较长。

迭代解法

既然递归法不够优雅，我们换一种方法。如果不用计算机计算，让你去算第n个斐波那契数，你会怎么做呢？

我想最简单直接的方法应该是：知道第一个和第二个后，计算第三个；知道第二个和第三个后，计算第四个，以此类推。

最终可以得到我们需要的结果。这种思路，没有冗余的计算。基于这个思路，我们的C语言实现如下：

/*fibo1.c*/

#include<stdio.h>

#include<stdlib.h>

/*求斐波那契数列迭代版*/

unsignedlongfibo(unsignedlongn)

{

unsignedlongpreVal = 1;

unsignedlongprePreVal = 0;

if(n <= 2)

returnn;

unsignedlongloop = 1;

unsignedlongreturnVal = 0;

while(loop < n)

{

returnVal = preVal +prePreVal;

/*更新记录结果*/

prePreVal = preVal;

preVal = returnVal;

loop++;

}

returnreturnVal;

}

/**main函数部分与fibo.c相同，这里省略*/

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

$ gcc -o fibo1 fibo1.c

$ time ./fibo1 50

the 50result is 12586269025

real0m0.002s

user 0m0.000s

sys 0m0.002s

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

尾递归解法

同样的思路，但是采用尾递归的方法来计算。

要计算第n个斐波那契数，我们可以先计算第一个，第二个，如果未达到n，则继续递归计算，尾递归C语言实现如下：

/*fibo2.c*/

#include<stdio.h>

#include<stdlib.h>

/*求斐波那契数列尾递归版*/

unsignedlongfiboProcess(unsignedlongn,unsignedlongprePreVal,unsignedlongpreVal,unsignedlongbegin)

{

/*如果已经计算到我们需要计算的，则返回*/

if(n == begin)

returnpreVal+prePreVal;

else

{

begin++;

returnfiboProcess(n,preVal,prePreVal+preVal,begin);

}

}

unsignedlongfibo(unsignedlongn)

{

if(n <= 1)

returnn;

else

returnfiboProcess(n,0,1,2);

}

/**main函数部分与fibo.c相同，这里省略*/

效率如何呢？

$ gcc -o fibo2 fibo2.c

$ time ./fibo2 50

the 50result is 12586269025

real0m0.002s

user 0m0.001s

sys 0m0.002s

可见，其效率并不逊于迭代法。尾递归在函数返回之前的最后一个操作仍然是递归调用。

尾递归的好处是，进入下一个函数之前，已经获得了当前函数的结果，因此不需要保留当前函数的环境，内存占用自然也是比最开始提到的递归要小。时间复杂度为O(n)。?

?

矩阵快速幂解法

这是一种高效的解法，需要推导，对此不感兴趣的可直接看最终推导结果。

下面的式子成立是显而易见的，不多做解释。

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

可以得到矩阵A：

因此也就可以得到下面的矩阵等式：

再进行变换如下：

以此类推，得到：

实际上f(n)就是矩A^(n-1)中的A[0][0],或者是矩A^n中的A[0][1]。

那么现在的问题就归结为，如何求A^n，其中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)

returnn;

MatrixTyperesult[][MAX_COL] = {1,0,0,1};

MatrixTypeA[][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相同，这里省略*/

该算法的关键部分在于对A^n的计算,它利用了我们开始提到的等式，对奇数和偶数分别处理。