斐波那契數(shù)列與遞歸的效率問題

學(xué)號：15051415

計(jì)算機(jī)科學(xué)與技術(shù)論文

C語言中FOR循環(huán)與遞歸的效率問題

學(xué)生姓名

馮冠璽

班級

院系

計(jì)算機(jī)科學(xué)與技術(shù)四班計(jì)算機(jī)學(xué)院

摘要：

在多數(shù)情況下，C語言中遞歸由于其易讀性(對于新手來說，還有可裝逼性)，而比較受到青睞。然而，在一些情況下，遞歸由于其效率的低下而嚴(yán)重影響到程序的用戶體驗(yàn)。

關(guān)鍵詞：C語言，效率，遞歸

下面通過一個簡單的程序來放大這種效率低下的問題：

實(shí)驗(yàn)平臺，工具：

在WIN10的平臺下，采用C-free5.0編譯器來編寫相應(yīng)的C程序，直觀地憑借輸出結(jié)果所需時間來比較遞歸與for循環(huán)的效率。

//該程序是求斐波那契數(shù)列第n個數(shù)的值

#include<stdio.h>

intdigui(intn)

{

if(n==1||n==2)

return1;

else

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

}

intmain()

{

inta;

scanf("%d”,&a);

printf("%d",digui(a));

}

經(jīng)過測試，當(dāng)n在37之后，開始出現(xiàn)人眼可觀的明顯卡頓。

〃通過FOR循環(huán)來計(jì)算

#include<stdio.h>intmain()

{

inta[100]={1,1},i,n;

scanf("%d",&n);

if(n==1||n==2)

printf("%d",a[n-1]);

if(n>=3){

for(i=2;i<n;i++)

a[i]=a[i-1]+a[i-2];

printf("%d",a[i-1]);

}

}

經(jīng)測試，在int整形數(shù)據(jù)類型所能輸出的數(shù)字范圍內(nèi)(即n小于等于48)，無任何卡頓。

那么為什么會出現(xiàn)這樣的情況？

許多問題是以遞歸的形式進(jìn)行解釋的，這只是因?yàn)樗确沁f歸形式更為清晰。但是，這些問題的迭代實(shí)現(xiàn)往往比遞歸實(shí)現(xiàn)效率更高，雖然代碼的可讀性可能稍差一些，當(dāng)一個問題相當(dāng)復(fù)雜，難以用迭代形式實(shí)現(xiàn)時，此時遞歸實(shí)現(xiàn)的簡潔性便可以補(bǔ)償它所帶來的，運(yùn)行時開銷。

然而，對于極端的情況(斐波那契數(shù)列)，它使用遞歸步驟計(jì)算digui(n-l)和digui(n-2)。但是，在計(jì)算digui(n-1)時也將計(jì)算digui(n-2)。每個遞歸調(diào)用都觸發(fā)另外兩個遞歸調(diào)用，而這兩個調(diào)用的任何一個還將觸發(fā)兩個遞歸調(diào)用，再接下去的調(diào)用也是如此。這樣，冗余計(jì)算的數(shù)量增長得非常快。例如，在遞歸計(jì)算digui(10)時，digui(3)的值被計(jì)算了21次。但是，在遞歸計(jì)算digui(30)時，digui(3)的值被計(jì)算了317811次。當(dāng)然，這317811次計(jì)算所產(chǎn)生的結(jié)果是完全一樣的，除了其中之一外，其余的純屬浪費(fèi)。這個額外的開銷是相當(dāng)恐怖的！

總結(jié)：

在編程時，具體問題要具