遞歸在C語言中的實(shí)現(xiàn)

筆者從事C語言程序設(shè)計(jì)教學(xué)多年，閱讀了不少關(guān)于C語言程序設(shè)計(jì)的教程，這些教程對遞歸算法的描述都比較簡單，并沒有就遞歸調(diào)用的遞推和回推過程做語句上的單步分析，只是用自然語言對算法過程做了簡單說明，這對學(xué)生去學(xué)習(xí)遞歸調(diào)用是很抽象的，短時(shí)間內(nèi)，學(xué)生很難掌握用遞歸技術(shù)來解決實(shí)際問題。因此，有必要對其進(jìn)行深入探討，分析其概念及算法結(jié)構(gòu)特點(diǎn)，分析其設(shè)計(jì)方法和實(shí)現(xiàn)過程，以此來幫助學(xué)生加深對遞歸算法思想的進(jìn)一步理解，學(xué)會正確的應(yīng)用遞歸解決實(shí)際問題。

一、遞歸算法的概念

計(jì)算機(jī)要完成人們預(yù)先定義的工作，首先應(yīng)該設(shè)計(jì)完成這個(gè)工作的步驟和方法，即算法。然后再根據(jù)算法編寫程序。算法是問題的求解過程的精確描述，求解一個(gè)問題往往有多種算法可供選擇，選擇標(biāo)準(zhǔn)首先是算法的正確性、可靠性、可讀性等，其次是算法所需存儲空間和時(shí)間的消耗。算法設(shè)計(jì)是一件非常復(fù)雜的事情，在處理實(shí)際問題時(shí)，為了更好地將復(fù)雜的問題變得簡單，在設(shè)計(jì)算法時(shí)常常采用遞歸的方法。

所謂遞歸，就是指用自身的結(jié)構(gòu)來描述自身，以實(shí)現(xiàn)層次數(shù)據(jù)結(jié)構(gòu)的查詢和訪問。用遞歸概念來描述的算法就稱為遞歸算法。在《C語言程序設(shè)計(jì)》第三版教程中，對遞歸的調(diào)用是用函數(shù)的方式來說明的，它指出：在調(diào)用一個(gè)函數(shù)的過程中又出現(xiàn)直接或者間接地調(diào)用該函數(shù)本身，稱為函數(shù)的遞歸調(diào)用。遞歸算法常用于遞歸調(diào)用方面，即函數(shù)自己調(diào)用自己。C語言允許一個(gè)自定義函數(shù)在函數(shù)的內(nèi)部調(diào)用自己，這樣的函數(shù)就叫遞歸函數(shù)。

二、遞歸算法的設(shè)計(jì)方法

遞歸算法既是一種有效的算法設(shè)計(jì)方法，也是一種有效的分析問題的方法。遞歸算法求解問題的基本思想是：對于較為復(fù)雜的問題，把原問題分解成若干個(gè)相對簡單且類同的子問題，這樣原問題就可遞推得到求解。

當(dāng)一個(gè)問題存在上述構(gòu)成遞歸的條件時(shí)，該問題便可以利用遞歸算法進(jìn)行處理。具體的設(shè)計(jì)方法是：當(dāng)所求解問題難于直接求解時(shí)，首先，把問題分解成若干個(gè)難度較小、較容易求解的子問題，子問題與原問題具有類同的結(jié)構(gòu)。如果子問題能夠直接求解，則解之；如果子問題仍不能直接求解，將每個(gè)子問題再分解成若干個(gè)更簡單的子問題，直到分解出的子問題能夠很容易地求解或解為已知，這是實(shí)現(xiàn)遞歸的模板。然后，設(shè)計(jì)遞歸出口（即結(jié)束遞歸的邊界條件），在滿足出口條件時(shí)，遞歸函數(shù)不能再調(diào)用自己，必須返回一個(gè)確定的值。將這兩個(gè)方面的問題分析好之后，就可以在子程序體中定義遞歸調(diào)用了。

在通常情況下，遞歸調(diào)用都是要受到條件控制的，而且在被調(diào)用的過程中，會對調(diào)用條件進(jìn)行有規(guī)律的修改，直到滿足邊界條件，返回邊界值，結(jié)束遞歸；然后按照原來的路徑逐層返回，求出原問題的解。由此可知，遞歸算法設(shè)計(jì)的關(guān)鍵在于遞歸描述和遞歸終止條件。

三、遞歸算法的實(shí)現(xiàn)過程

遞歸算法的執(zhí)行過程是不斷地自調(diào)用，直到到達(dá)遞歸出口才結(jié)束。然后，遞歸算法開始按最后調(diào)用的過程最先返回的次序逐層返回，返回到最外層的調(diào)用語句時(shí)遞歸算法執(zhí)行過程結(jié)束。可見，遞歸的實(shí)現(xiàn)過程包含了“調(diào)用”（或者叫遞推）和“返回”（或者叫回推）兩個(gè)階段。

許多問題都是可以利用遞歸算法進(jìn)行求解的。C語言中一個(gè)最常用例子就是計(jì)算n!

用遞歸法計(jì)算n!可用下述公式表示：

n!=1（n=0，1）

n×（n-1）! （n>1）

按公式可編程如下：

#include

#include

long ff（int n） /*遞歸函數(shù)*/

{

long f；

if（n<0） printf（\"n<0，input error\"）；

else if（n==0||n==1） f=1；

else if=ff（n-1）*n； /*調(diào)用ff（）函數(shù)*/

return（f）；

}

main（）

{

int n；

long y；

printf（\"\input a inteager number：\\"）；

scanf（\"%d\"，n）；

y=ff（n）；

printf（\"%d!=%ld\"，n，y）；

}

程序中給出的函數(shù)ff是一個(gè)遞歸函數(shù)。主函數(shù)調(diào)用ff 后即進(jìn)入函數(shù)ff執(zhí)行，如果n<0，n==0或n=1時(shí)都將結(jié)束函數(shù)的執(zhí)行，否則就遞歸調(diào)用ff函數(shù)自身。由于每次遞歸調(diào)用的實(shí)參為n-1，即把n-1的值賦予形參n，最后當(dāng)n-1的值為1時(shí)再作遞歸調(diào)用，形參n的值也為1，將使遞歸終止。然后可逐層退回。

上例也可以不用遞歸的方法來完成。如可以用循環(huán)結(jié)構(gòu)，即從1開始乘以2，再乘以3……直到n。循環(huán)結(jié)構(gòu)比遞歸法更容易理解和實(shí)現(xiàn)。但是有些問題則只能用遞歸算法才能實(shí)現(xiàn)。典型的問題是Hanoi塔問題。

有些問題無法直接使用遞歸公式，而要通過一個(gè)遞歸過程來描述。例如，大家所熟知的漢諾塔問題：一塊板上有三根針，A，B，C。A針上套有64個(gè)大小不等的圓盤，大的在下，小的在上。要把這64個(gè)圓盤從A針移動(dòng)C針上，每次只能移動(dòng)一個(gè)圓盤，移動(dòng)可以借助B針進(jìn)行。但在任何時(shí)候，任何針上的圓盤都必須保持大盤在下，小盤在上。求移動(dòng)的步驟。

可編程如下：

move（int n，int x，int y，int z）

{

if（n==1）

printf（\"%c-->%c\\"，x，z）；

else

{

move（n-1，x，z，y）；

printf（\"%c-->%c\\"，x，z）；

move（n-1，y，x，z）；

}

}

main（）

{

int h；

printf（\"\input number：\\"）；

scanf（\"%d\"，h）；

printf（\"the step to moving %2d diskes：\\"，h）；

move（h，'a'，'b'，'c'）；

}

從程序中可以看出，move函數(shù)是一個(gè)遞歸函數(shù)，它有四個(gè)形參n，x，y，z。n表示圓盤數(shù)，x，y，z分別表示三根針。move 函數(shù)的功能是把x上的n個(gè)圓盤移動(dòng)到z上。當(dāng)n==1時(shí)，直接把x上的圓盤移至z上，輸出x→z。如n!=1則分為三步：遞歸調(diào)用move函數(shù)，把n-1個(gè)圓盤從x移到y(tǒng)；輸出x→z；遞歸調(diào)用move函數(shù)，把n-1個(gè)圓盤從y移到z。在遞歸調(diào)用過程中n=n-1，故n的值逐次遞減，最后n=1時(shí)，終止遞歸，逐層返回。

此程序根據(jù)對問題的遞歸描述寫出，結(jié)構(gòu)清楚，易理解。因涉及遞歸，所以其調(diào)用的執(zhí)行過程可能很復(fù)雜。但如果不用遞歸方法，問題又可能很難處理。因此，在算法描述過程中，只需把以上算法的三步過程設(shè)計(jì)好，再考慮一個(gè)盤子時(shí)的情況（遞歸出口）怎樣處理就可以了。

從上述分析中，可以認(rèn)為，看問題能否用遞歸算法，先不要考慮具體的執(zhí)行過程，只要滿足上述構(gòu)成遞歸的條件即可。在C程序設(shè)計(jì)中使用遞歸時(shí)還應(yīng)注意，在定義遞歸函數(shù)時(shí)，一般先使用if語句進(jìn)行遞歸測試，找到遞歸結(jié)束的條件，然后再進(jìn)行遞歸調(diào)用。

以上示例是遞歸應(yīng)用的典型。很多人認(rèn)為遞歸不易理解，這是把遞歸狹隘化了，但是對遞歸的理解不能因此受到限制，遞歸程序的復(fù)雜程度比一般程序要高很多。遞歸算法使程序 清晰直觀，是程序設(shè)計(jì)中很重要的方面，但遞歸在計(jì)算機(jī)中的執(zhí)行過程卻很復(fù)雜，需要占用較大的內(nèi)存空間和較多的系統(tǒng)時(shí)間來進(jìn)行頻繁進(jìn)出和轉(zhuǎn)移操作，執(zhí)行效率很低。所以，在C程序設(shè)計(jì)過程中，并不一味追求遞歸。如果一個(gè)問題的求解過程明顯是通過循環(huán)處理方法即可方便解決的，則不必要使用遞歸。反之，在對問題進(jìn)行分解、求解的過程中得到的是和原問題性質(zhì)相同的子問題，由此自然得到一個(gè)遞歸算法，且它比實(shí)現(xiàn)非遞歸算法更符合人們的思維邏輯，則應(yīng)該使用遞歸。因此，使用遞歸應(yīng)揚(yáng)長避短，只有真正掌握遞歸這個(gè)有效的編程方法，才能提高編程能力和編程效率。