C語言用遞歸求斐波那契數，讓你發現遞歸的缺陷和效率瓶頸

分享到：

QQ空間

新浪微博

騰訊微博

豆瓣

人人網

遞歸是一種強有力的技巧，但和其他技巧一樣，它也可能被誤用。

一般需要遞歸解決的問題有兩個特點：

• 存在限制條件，當符合這個條件時遞歸便不再繼續；
• 每次遞歸調用之后越來越接近這個限制條件。

遞歸使用最常見的一個例子就是求階乘，具體描述和代碼請看這里：C語言遞歸和迭代法求階乘

但是，遞歸函數調用將涉及一些運行時開銷——參數必須壓到堆棧中，為局部變量分配內存空間（所有遞歸均如此，并非特指求階乘這個例子），寄存器的值必須保存等。當遞歸函數的每次調用返回時，上述這些操作必須還原，恢復成原來的樣子。所以， 基于這些開銷，對于遞歸求階乘而言，它并沒有簡化問題的解決方案。

迭代求階乘使用簡單循環的程序，看上去不甚符合前面階乘的數學定義，但它卻能更為有效地計算出結果。如果你仔細觀察遞歸函數，你會發現遞歸調用是函數所執行的最后一項任務。這個函數是尾部遞歸(tail recursion)的一個例子。由于函數在遞歸調用返回之后不再執行任何任務，所以尾部遞歸可以很方便地轉換成一個簡單循環，完成相同的任務。

提示：許多問題是以遞歸的形式進行解釋的，這只是因為它比非遞歸形式更為清晰。但是，這些問題的迭代實現往往比遞歸實現效率更高，雖然代碼的可讀性可能稍差一些，當一個問題相當復雜，難以用迭代形式實現時，此時遞歸實現的簡潔性便可以補償它所帶來的運行時開銷。

這里有一個更為極端的例子，菲波那契數就是一個數列，數列中每個數的值就是它前面兩個數的和。 這種關系常常用遞歸的形式進行描述：


同樣，這種遞歸形式的定義容易誘導人們使用遞歸形式來解決問題。這里有一個陷牌：它使用遞歸步驟計算Fibonacci(n-1)和Fibonacci(n-2)。但是，在計算Fibonacci(n-1)時也將計算Fibonacci(n-2)。這個額外的計算代價有多大呢？

答案是，它的代價遠遠不止一個冗余計算：每個遞歸調用都觸發另外兩個遞歸調用，而這兩個調用的任何一個還將觸發兩個遞歸調用，再接下去的調用也是如此。這樣，冗余計算的數量增長得非常快。例如，在遞歸計算Fibonacci(10)時，Fibonacci(3)的值被計算了21次。但是，在遞歸計算 Fibonacci(30)時，Fibonacci(3)的值被計算了317811次。當然，這317811次計算所產生的結果是完全一樣的，除了其中之一外，其余的純屬浪費。這個額外的開銷真是相當恐怖！

如果使用一個簡單循環來代替遞歸，這個循環的形式肯定不如遞歸形式符合前面菲波那契數的抽象定義，但它的效率提高了幾十萬倍！

當你使用遞歸方式實現一個函數之前，先問問你自己使用遞歸帶來的好處是否抵得上它的代價。 而且你必須小心：這個代價可能比初看上去要大得多。

不信請看下面的代碼，分別用遞歸和迭代計算斐波那契數，效率差距真是大的驚人。 復制純文本復制

#include <stdio.h>

#include <time.h>

#include <windows.h>

?

// 遞歸計算斐波那契數

long fibonacci_recursion( int n )

{

if( n <= 2 )

return 1;

?

return fibonacci_recursion(n-1) + fibonacci_recursion(n-2);

}

?

// 迭代計算斐波那契數

long fibonacci_iteration( int n )

{

long result;

long previous_result;

long next_older_result;

?

result = previous_result = 1;

?

while( n > 2 ){

n -= 1;

next_older_result = previous_result;

previous_result = result;

result = previous_result + next_older_result;

}

return result;

}

?

int main(){

int N = 45;

?

// 遞歸消耗的時間

clock_t recursion_start_time = clock();

long result_recursion = fibonacci_recursion(N);

clock_t recursion_end_time = clock();

?

// 迭代消耗的時間

clock_t iteration_start_time = clock();

long result_iteration = fibonacci_iteration(N);

clock_t iteration_end_time = clock();

?

// 輸出遞歸消耗的時間

printf("Result of recursion: %ld \nTime: %fseconds",

fibonacci_recursion(N),

(double)(recursion_end_time-recursion_start_time)/CLOCKS_PER_SEC

);

printf("\n-----------------------\n");

// 輸出迭代消耗的時間

printf("Result of iteration: %ld \nTime: %fseconds",

fibonacci_iteration(N),

(double)(iteration_end_time-iteration_start_time)/CLOCKS_PER_SEC

);

?

return 0;

}

#include <stdio.h> #include <time.h> #include <windows.h>// 遞歸計算斐波那契數 long fibonacci_recursion( int n ) {if( n <= 2 )return 1;return fibonacci_recursion(n-1) + fibonacci_recursion(n-2); }// 迭代計算斐波那契數 long fibonacci_iteration( int n ) {long result;long previous_result;long next_older_result;result = previous_result = 1;while( n > 2 ){n -= 1;next_older_result = previous_result;previous_result = result;result = previous_result + next_older_result;}return result; }int main(){int N = 45;// 遞歸消耗的時間clock_t recursion_start_time = clock();long result_recursion = fibonacci_recursion(N);clock_t recursion_end_time = clock();// 迭代消耗的時間clock_t iteration_start_time = clock();long result_iteration = fibonacci_iteration(N);clock_t iteration_end_time = clock();// 輸出遞歸消耗的時間printf("Result of recursion: %ld \nTime: %fseconds",fibonacci_recursion(N),(double)(recursion_end_time-recursion_start_time)/CLOCKS_PER_SEC);printf("\n-----------------------\n");// 輸出迭代消耗的時間printf("Result of iteration: %ld \nTime: %fseconds",fibonacci_iteration(N),(double)(iteration_end_time-iteration_start_time)/CLOCKS_PER_SEC);return 0; } 運行結果： Result of recursion: 1134903170 Time: 7.494000 seconds --------------------------------------- Result of iteration: 1134903170 Time: 0.000000 seconds
注意：上面的程序最好在GCC（Linux下的GCC或Windows下的Code:Blocks）下運行，VC下可能統計不到運行時間。

看吧，用遞歸花了將近7.5秒的時間，但是用迭代幾乎不費吹灰之力，效率快到統計不到運行時間。 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的C语言用递归求斐波那契数，让你发现递归的缺陷和效率瓶颈的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。