原標(biāo)題：求職干貨：再也不怕面試官問斐波那契數(shù)列了！

??

作者 | 守望

責(zé)編 | 胡巍巍

前言

假如面試官讓你編寫求斐波那契數(shù)列的代碼時，是不是心中暗喜?不就是遞歸么，早就會了。如果真這么想，那就危險了。

遞歸解法

遞歸，在數(shù)學(xué)與計算機科學(xué)中，是指在函數(shù)的定義中使用函數(shù)自身的方法。

斐波那契數(shù)列的計算表達式很簡單：

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

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

因此，我們能很快根據(jù)表達式寫出遞歸版的代碼：

/*fibo.c*/

#include<stdio.h>

#include<stdlib.h>

/*求斐波那契數(shù)列遞歸版*/

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;

}

關(guān)鍵代碼只有4行。簡潔明了，一氣呵成。

編譯：

gcc-ofibofibo.c

運行計算第5個斐波那契數(shù)：

$ time ./fibo 5

the 5result is 5

real0m0.001s

user 0m0.001s

sys 0m0.000s

看起來并沒有什么不妥，運行時間也很短。

繼續(xù)計算第50個斐波那契數(shù)列：

$ time ./fibo 50

the 50result is 12586269025

real1m41.655s

user 1m41.524s

sys 0m0.076s

計算第50個斐波那契數(shù)的時候，竟然將近兩多鐘！

遞歸分析

為什么計算第50個的時候竟然需要1分多鐘。

我們仔細分析我們的遞歸算法，就會發(fā)現(xiàn)問題，當(dāng)我們計算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)的結(jié)果，fibo(0)被計算了3次，fibo(1)被計算了5次，fibo(2)被計算了2次�？梢钥吹剑�它的計算次數(shù)幾乎是指數(shù)級的！

因此，雖然遞歸算法簡潔，但是在這個問題中，它的時間復(fù)雜度卻是難以接受的。

除此之外，遞歸函數(shù)調(diào)用的越來越深，它們在不斷入棧卻遲遲不出棧，空間需求越來越大，雖然訪問速度高，但大小是有限的，最終可能導(dǎo)致棧溢出。

在linux中，我們可以通過下面的命令查看�？臻g的軟限制：

$ulimit-s

8192

可以看到，默認(rèn)�？臻g大小只有8M。

一般來說，8M的�？臻g對于一般程序完全足夠。如果8M的�？臻g不夠使用，那么就需要重新審視你的代碼設(shè)計了。

遞歸改進版

既然我們知道最初版本的遞歸存在大量的重復(fù)計算，那么我們完全可以考慮將已經(jīng)計算的值保存起來，從而避免重復(fù)計算，該版本代碼實現(xiàn)如下：

/*fibo0.c*/

#include<stdio.h>

#include<stdlib.h>

/*求斐波那契數(shù)列，避免重復(fù)計算版本*/

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;

/*申請數(shù)組用于保存已經(jīng)計算過的內(nèi)容*/

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函數(shù)部分與fibo.c相同，這里省略*/

效率如何呢？

$ gcc -o fibo0 fibo0.c

$ time ./fibo0 50

the 50result is 12586269025

real0m0.002s

user 0m0.000s

sys 0m0.002s

可見其效率還是不錯的，時間復(fù)雜度為O(n)。

但是特別注意的是，這種改進版的遞歸，雖然避免了重復(fù)計算，但是調(diào)用鏈仍然比較長。

迭代解法

既然遞歸法不夠優(yōu)雅，我們換一種方法。如果不用計算機計算，讓你去算第n個斐波那契數(shù)，你會怎么做呢？

我想最簡單直接的方法應(yīng)該是：知道第一個和第二個后，計算第三個；知道第二個和第三個后，計算第四個，以此類推。

最終可以得到我們需要的結(jié)果。這種思路，沒有冗余的計算。基于這個思路，我們的C語言實現(xiàn)如下：

/*fibo1.c*/

#include<stdio.h>

#include<stdlib.h>

/*求斐波那契數(shù)列迭代版*/

unsignedlongfibo(unsignedlongn)

{

unsignedlongpreVal = 1;

unsignedlongprePreVal = 0;

if(n <= 2)

returnn;

unsignedlongloop = 1;

unsignedlongreturnVal = 0;

while(loop < n)

{

returnVal = preVal +prePreVal;

/*更新記錄結(jié)果*/

prePreVal = preVal;

preVal = returnVal;

loop++;

}

returnreturnVal;

}

/**main函數(shù)部分與fibo.c相同，這里省略*/

編譯并計算第50個斐波那契數(shù)：

$ gcc -o fibo1 fibo1.c

$ time ./fibo1 50

the 50result is 12586269025

real0m0.002s

user 0m0.000s

sys 0m0.002s

可以看到，計算第50個斐波那契數(shù)只需要0.002s！時間復(fù)雜度為O(n)。

尾遞歸解法

同樣的思路，但是采用尾遞歸的方法來計算。

要計算第n個斐波那契數(shù)，我們可以先計算第一個，第二個，如果未達到n，則繼續(xù)遞歸計算，尾遞歸C語言實現(xiàn)如下：

/*fibo2.c*/

#include<stdio.h>

#include<stdlib.h>

/*求斐波那契數(shù)列尾遞歸版*/

unsignedlongfiboProcess(unsignedlongn,unsignedlongprePreVal,unsignedlongpreVal,unsignedlongbegin)

{

/*如果已經(jīng)計算到我們需要計算的，則返回*/

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函數(shù)部分與fibo.c相同，這里省略*/

效率如何呢？

$ gcc -o fibo2 fibo2.c

$ time ./fibo2 50

the 50result is 12586269025

real0m0.002s

user 0m0.001s

sys 0m0.002s

可見，其效率并不遜于迭代法。尾遞歸在函數(shù)返回之前的最后一個操作仍然是遞歸調(diào)用。

尾遞歸的好處是，進入下一個函數(shù)之前，已經(jīng)獲得了當(dāng)前函數(shù)的結(jié)果，因此不需要保留當(dāng)前函數(shù)的環(huán)境，內(nèi)存占用自然也是比最開始提到的遞歸要小。時間復(fù)雜度為O(n)。?

?

矩陣快速冪解法

這是一種高效的解法，需要推導(dǎo)，對此不感興趣的可直接看最終推導(dǎo)結(jié)果。

下面的式子成立是顯而易見的，不多做解釋。

如果a為矩陣，等式同樣成立，后面我們會用到它。假設(shè)有矩陣2*2矩陣A，滿足下面的等式：

可以得到矩陣A：

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

再進行變換如下：

以此類推，得到：

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

那么現(xiàn)在的問題就歸結(jié)為，如何求A^n，其中A為2*2的矩陣。

根據(jù)我們最開始的公式，很容易就有思路，代碼實現(xiàn)如下：

/*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矩陣乘法，這里沒有寫成通用形式，有興趣的可以自己實現(xiàn)通用矩陣乘法*/

int matrixDot(MatrixType A[MAX_ROW][MAX_COL],MatrixType B[MAX_ROW][MAX_COL],MatrixType C[MAX_ROW][MAX_COL])

{

/*C為返回結(jié)果，由于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函數(shù)部分與fibo.c相同，這里省略*/

該算法的關(guān)鍵部分在于對A^n的計算,它利用了我們開始提到的等式，對奇數(shù)和偶數(shù)分別處理。