遞歸在C語言中的實現

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

一、遞歸算法的概念

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

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

二、遞歸算法的設計方法

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

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

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

三、遞歸算法的實現過程

遞歸算法的執行過程是不斷地自調用，直到到達遞歸出口才結束。然后，遞歸算法開始按最后調用的過程最先返回的次序逐層返回，返回到最外層的調用語句時遞歸算法執行過程結束?？梢姡f歸的實現過程包含了“調用”（或者叫遞推）和“返回”（或者叫回推）兩個階段。

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

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

n!=1（n=0，1）

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

按公式可編程如下：

#include

#include

long ff（int n） /*遞歸函數*/

{

long f；

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

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

else if=ff（n-1）*n； /*調用ff（）函數*/

return（f）；

}

main（）

{

int n；

long y；

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

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

y=ff（n）；

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

}

程序中給出的函數ff是一個遞歸函數。主函數調用ff 后即進入函數ff執行，如果n<0，n==0或n=1時都將結束函數的執行，否則就遞歸調用ff函數自身。由于每次遞歸調用的實參為n-1，即把n-1的值賦予形參n，最后當n-1的值為1時再作遞歸調用，形參n的值也為1，將使遞歸終止。然后可逐層退回。

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

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

可編程如下：

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函數是一個遞歸函數，它有四個形參n，x，y，z。n表示圓盤數，x，y，z分別表示三根針。move 函數的功能是把x上的n個圓盤移動到z上。當n==1時，直接把x上的圓盤移至z上，輸出x→z。如n!=1則分為三步：遞歸調用move函數，把n-1個圓盤從x移到y；輸出x→z；遞歸調用move函數，把n-1個圓盤從y移到z。在遞歸調用過程中n=n-1，故n的值逐次遞減，最后n=1時，終止遞歸，逐層返回。

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

從上述分析中，可以認為，看問題能否用遞歸算法，先不要考慮具體的執行過程，只要滿足上述構成遞歸的條件即可。在C程序設計中使用遞歸時還應注意，在定義遞歸函數時，一般先使用if語句進行遞歸測試，找到遞歸結束的條件，然后再進行遞歸調用。

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