關(guān)于遞歸與遞推的討論

摘 要: 遞推一般用循環(huán)來(lái)解決，從已知條件到未知逐漸接近結(jié)果;遞歸一般自己調(diào)用自己，從未知到已知，把規(guī)模大的、較難解決的問(wèn)題變成規(guī)模較小的、易解決的同一問(wèn)題。規(guī)模較小的問(wèn)題又變成規(guī)模更小的問(wèn)題，并且小到一定程度可以直接得出它的解，從而得到原來(lái)問(wèn)題的解。

關(guān)鍵詞: 遞歸 遞推 算法

一、前言

遞歸和遞推都是算法設(shè)計(jì)中的難點(diǎn)，算法又十分相近，很多學(xué)生誤認(rèn)為是一回事，非常容易混淆。其實(shí)它們之間既有相似點(diǎn)，又有明顯的區(qū)別。下面筆者從一個(gè)簡(jiǎn)單的階乘實(shí)例進(jìn)行分析。

二、用遞歸法解階乘

數(shù)學(xué)上經(jīng)常這樣描述:f(n)=1n=0，n=1n×f(1-1)n>1。

算法設(shè)計(jì):

long f(int n)

{if(n=0||n=1)

return 1;

else

return n*f(n-1);

}

以上算法中，在調(diào)用函數(shù)f(n)的過(guò)程中又調(diào)用自身f(n-1)，這樣在一個(gè)子程序(過(guò)程或函數(shù))的定義中直接或間接地調(diào)用該子程序本身，稱為遞歸。顯然，遞歸是一種非常有用的程序設(shè)計(jì)方法。用遞歸算法編寫的程序結(jié)構(gòu)清晰，具有很好的可讀性。

遞歸算法的基本思想是:把規(guī)模大的、較難解決的問(wèn)題變成規(guī)模較小的、易解決的同一問(wèn)題。規(guī)模較小的問(wèn)題又變成規(guī)模更小的問(wèn)題，并且小到一定程度可以直接得出它的解，從而得到原來(lái)問(wèn)題的解。我們利用遞歸算法解題，首先要對(duì)問(wèn)題的以下三個(gè)方面進(jìn)行分析:

1.決定問(wèn)題規(guī)模的參數(shù)。需要用遞歸算法解決的問(wèn)題，其規(guī)模通常都是比較大的，在問(wèn)題中決定規(guī)模大小(或問(wèn)題復(fù)雜程度)的量有哪些?把它們找出來(lái)。

2.問(wèn)題的邊界條件及邊界值(又叫結(jié)束條件或出口)。在什么情況下可以直接得出問(wèn)題的解?這就是問(wèn)題的邊界條件及邊界值。

3.解決問(wèn)題的通式(又叫遞歸體)。把規(guī)模大的、較難解決的問(wèn)題變成規(guī)模較小、易解決的同一問(wèn)題，需要通過(guò)哪些步驟或等式來(lái)實(shí)現(xiàn)?這是解決遞歸問(wèn)題的難點(diǎn)。把這些步驟或等式確定下來(lái)。

我們把以上三個(gè)方面分析好之后，就可以在子程序中定義遞歸調(diào)用。例如上面階乘的例子中:n=1或n=0時(shí)的階乘值是1，此時(shí)n為1或0就是遞歸出口。f(n)=n×f(n-1)便是遞歸體。

可見遞歸是一種思想，是一種把原問(wèn)題復(fù)雜度進(jìn)一步降低以后再求解的思路，這個(gè)定義本身就有“遞歸性”，遞歸性指的是一種特征:函數(shù)或者過(guò)程還是什么，自身計(jì)算的時(shí)候，調(diào)用到自身的特征。遞歸會(huì)把原問(wèn)題的未知撥開“一層”，越來(lái)越接近已知，而此時(shí)遞歸算法根本沒(méi)有算出一個(gè)中間量，在遞歸深度達(dá)到最大的時(shí)候，達(dá)到已知條件，然后已知條件作為上一層的已知，一層一層地返回，最后未知就這樣被求解。另外遞歸的算法進(jìn)棧和回溯思想結(jié)合。

三、用遞推法解階乘

數(shù)學(xué)上一般這樣描述:n!=1×2×3×4×…×(n-1)×n。

算法設(shè)計(jì):

longf(int n)

{long s=1;

int i;

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

s=s*i;

return s;

}

可見遞推也是一種思想，是從已知條件出發(fā)，用一種具體的算法，一步一步接近未知，一般采用循環(huán)結(jié)構(gòu)。遞推算法在求解的過(guò)程中，每一個(gè)中間量都是已知，而且沒(méi)有重復(fù)計(jì)算，運(yùn)算簡(jiǎn)潔，但是書寫代碼和理解代碼比較難。

四、遞歸和遞推的區(qū)別

遞歸是利用子問(wèn)題與父問(wèn)題的關(guān)系，進(jìn)而構(gòu)造成有遞歸性的函數(shù)。而遞推恰恰與此相反，從已知到未知，類似于一般解數(shù)學(xué)題的思路。從未知與已知的順序上來(lái)看，它們好像是逆過(guò)程，但其實(shí)不是，遞歸把問(wèn)題簡(jiǎn)單化，抓的是問(wèn)題與子問(wèn)題的聯(lián)系，而遞推是把中間解推進(jìn)，抓得是中間量與更靠近未知的中間量的聯(lián)系，兩者不同，所以不能看成逆過(guò)程。

我們?cè)倏匆粋€(gè)例子:斐波那契數(shù)列:1，1，2，3，5，8，13，21……公式F(n)=F(n-1)+F(n-2)，F(xiàn)(1)=F(2)=1;這個(gè)公式本身是具有遞歸性的。

1.遞歸解

long f(int n)

{if(n<=2)

return 1;

else

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

}

這行代碼充分地顯示了遞歸算法的簡(jiǎn)潔。

2.遞推解

long f(int n)

{long t;f1=1，f2=1;

if(n<=2)reutrn 1;

for(int i=3;i<=n;i++)

{t=f1+f2;

f1=f2;

f2=t;

}

}

五、結(jié)語(yǔ)

由此可見，遞歸重在“歸”，你要求的是什么，就直接求什么，至于要怎么去調(diào)用、怎么去求，讓函數(shù)自己一步一步去反復(fù)調(diào)用;遞推重在“推”，是按照我們平時(shí)做數(shù)學(xué)的方法來(lái)算。編程時(shí)遞歸比較特殊，表現(xiàn)在函數(shù)自身調(diào)用自身，這樣編程代碼緊湊，程序的可讀性好，但效率低，還可能導(dǎo)致堆棧溢出，特別是遞歸層次比較多時(shí)。一般來(lái)說(shuō)，遞歸程序都可以用循環(huán)程序?qū)崿F(xiàn)，用循環(huán)程序?qū)崿F(xiàn)雖然較難理解，但安全可靠。

參考文獻(xiàn):

[1]譚浩強(qiáng).C程序設(shè)計(jì)(第二版).清華大學(xué)出版社.

[2]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版).清華大學(xué)出版社.