前言
假如面試官讓你編寫求斐波那契數(shù)列的代碼時毅往，是不是心中暗喜?不就是遞歸么攀唯，早就會了。如果真這么想侯嘀，那就危險了戒幔。
遞歸求斐波那契數(shù)列
遞歸，在數(shù)學與計算機科學中工坊，是指在函數(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ù)列遞歸版*/
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個斐波那契數(shù)：
$ time ./fibo 5
the 5 result is 5
real 0m0.001s
user 0m0.001s
sys 0m0.000s
看起來并沒有什么不妥吁伺，運行時間也很短租谈。
繼續(xù)計算第50個斐波那契數(shù)列：
$ time ./fibo 50
the 50 result is 12586269025
real 1m41.655s
user 1m41.524s
sys 0m0.076s
計算第50個斐波那契數(shù)的時候割去，竟然花了一分多鐘！
遞歸分析
為什么計算第50個的時候竟然需要1分多鐘夸赫。我們仔細分析我們的遞歸算法咖城，就會發(fā)現(xiàn)問題，當我們計算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次≈椋可以看到恬惯，它的計算次數(shù)幾乎是指數(shù)級的！
因此浓恳，雖然遞歸算法簡潔颈将，但是在這個問題中言疗，它的時間復雜度卻是難以接受的。除此之外疑务，遞歸函數(shù)調(diào)用的越來越深梗醇，它們在不斷入棧卻遲遲不出棧叙谨，空間需求越來越大，雖然訪問速度高涤垫，但大小是有限的竟终，最終可能導致棧溢出。
在linux中榆芦，我們可以通過下面的命令查看棧空間的軟限制：
$ ulimit -s
8192
可以看到驻右，默認椘榇荆空間大小只有8M拣凹。一般來說，8M的椶置兀空間對于一般程序完全足夠祈惶。如果8M的椗跚耄空間不夠使用，那么就需要重新審視你的代碼設計了疹蛉。
迭代解法
既然遞歸法不夠優(yōu)雅可款，我們換一種方法。如果不用計算機計算筋讨，讓你去算第n個斐波那契數(shù)摸恍，你會怎么做呢立镶？我想最簡單直接的方法應該是：知道第一個和第二個后，計算第三個嗜逻；知道第二個和第三個后缭召，計算第四個，以此類推妨蛹。最終可以得到我們需要的結果蛙卤。這種思路噩死，沒有冗余的計算已维。基于這個思路栅屏，我們的C語言實現(xiàn)如下：
/*fibo1.c*/
#include <stdio.h>
#include <stdlib.h>
/*求斐波那契數(shù)列迭代版*/
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函數(shù)部分與fibo.c相同堂鲜，這里省略*/
編譯并計算第50個斐波那契數(shù)：
$ gcc -o fibo1 fibo1.c
$ time ./fibo1 50
the 50 result is 12586269025
real 0m0.002s
user 0m0.001s
sys 0m0.002s
可以看到缔莲，計算第50個斐波那契數(shù)只需要0.002s！時間復雜度為O(n)蛀骇。
尾遞歸解法
同樣的思路读拆，但是采用尾遞歸的方法來計算建椰。要計算第n個斐波那契數(shù)，我們可以先計算第一個屠列，第二個伞矩，如果未達到n乃坤，則繼續(xù)遞歸計算沟蔑，尾遞歸C語言實現(xiàn)如下：
/*fibo2.c*/
#include <stdio.h>
#include <stdlib.h>
/*求斐波那契數(shù)列尾遞歸版*/
unsigned long fiboProcess(unsigned long n,unsigned long prePreVal,unsigned long preVal,unsigned long begin)
{
/*如果已經(jīng)計算到我們需要計算的狱杰，則返回*/
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函數(shù)部分與fibo.c相同瘦材，這里省略*/
效率如何呢？
$ gcc -o fibo2 fibo2.c
$ time ./fibo2 50
the 50 result is 12586269025
real 0m0.002s
user 0m0.001s
sys 0m0.002s
可見仿畸，其效率并不遜于迭代法食棕。尾遞歸在函數(shù)返回之前的最后一個操作仍然是遞歸調(diào)用。尾遞歸的好處是错沽，進入下一個函數(shù)之前簿晓，已經(jīng)獲得了當前函數(shù)的結果，因此不需要保留當前函數(shù)的環(huán)境千埃，內(nèi)存占用自然也是比最開始提到的遞歸要小憔儿。時間復雜度為O(n)。
遞歸改進版
既然我們知道最初版本的遞歸存在大量的重復計算放可，那么我們完全可以考慮將已經(jīng)計算的值保存起來，從而避免重復計算吴侦，該版本代碼實現(xiàn)如下：
/*fibo3.c*/
#include <stdio.h>
#include <stdlib.h>
/*求斐波那契數(shù)列屋休，避免重復計算版本*/
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;
/*申請數(shù)組用于保存已經(jīng)計算過的內(nèi)容*/
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函數(shù)部分與fibo.c相同，這里省略*/
效率如何呢备韧？
$ gcc -o fibo3 fibo3.c
$ time ./fibo3 50
the 50 result is 12586269025
real 0m0.002s
user 0m0.002s
sys 0m0.001s
可見效率是不遜于其他兩種優(yōu)化算法的劫樟。但是特別注意的是，這種改進版的遞歸织堂，雖然避免了重復計算叠艳，但是調(diào)用鏈仍然比較長。
其他解法
其他兩種時間復雜度為O(logn)的矩陣解法以及O(1)的通項表達式解法本文不介紹易阳。歡迎留言補充附较。
總結
總結一下遞歸的優(yōu)缺點：
優(yōu)點：
- 實現(xiàn)簡單
- 可讀性好
缺點：
- 遞歸調(diào)用，占用空間大
- 遞歸太深潦俺，易發(fā)生棧溢出
- 可能存在重復計算
可以看到拒课，對于求斐波那契數(shù)列的問題，使用一般的遞歸并不是一種很好的解法事示。
所以早像，當你使用遞歸方式實現(xiàn)一個功能之前，考慮一下使用遞歸帶來的好處是否抵得上它的代價肖爵。
更多解法請參考 https://www.yanbinghu.com/2019/01/07/16863.html
微信公眾號【編程珠璣】：專注但不限于分享計算機編程基礎卢鹦，Linux，C語言劝堪，C++冀自，算法揉稚，數(shù)據(jù)庫等編程相關[原創(chuàng)]技術文章，號內(nèi)包含大量經(jīng)典電子書和視頻學習資源熬粗。歡迎一起交流學習搀玖，一起修煉計算機“內(nèi)功”，知其然荐糜，更知其所以然巷怜。
