孫道層

（德宏職業(yè)學(xué)院 云南省芒市 678400）

1 前言

在C語(yǔ)言程序設(shè)計(jì)中，如果一個(gè)函數(shù)直接或者間接地調(diào)用自身，那么這種調(diào)用就被稱之為遞歸調(diào)用，遞歸調(diào)用是嵌套調(diào)用的特例[1-2]。遞歸算法在程序設(shè)計(jì)中得到廣泛的應(yīng)用，通過函數(shù)遞歸的調(diào)用可以將非常復(fù)雜的問題轉(zhuǎn)換為規(guī)模較小簡(jiǎn)單相似的問題，層層遞進(jìn)，最終求解[3]。函數(shù)遞歸算法策略大大減少程序的代碼量，函數(shù)通過遞歸調(diào)用本身可以實(shí)現(xiàn)解決問題過程所需要的重復(fù)計(jì)算。研究C語(yǔ)言程序設(shè)計(jì)函數(shù)遞歸算法，有利于正確使用函數(shù)遞歸進(jìn)行程序設(shè)計(jì)，降低程序運(yùn)行的時(shí)間復(fù)雜度和空間復(fù)雜度，提高程序執(zhí)行效率[4-5]。

2 函數(shù)遞歸算法的特征

函數(shù)遞歸調(diào)用本身時(shí)，會(huì)在計(jì)算機(jī)內(nèi)部存儲(chǔ)結(jié)構(gòu)中開辟一個(gè)棧，對(duì)函數(shù)調(diào)用現(xiàn)場(chǎng)發(fā)起保護(hù)，并將函數(shù)調(diào)用時(shí)的參數(shù)和局部變量保存到新分配的存儲(chǔ)空間，函數(shù)調(diào)用結(jié)束返回時(shí)，計(jì)算機(jī)會(huì)自動(dòng)釋放函數(shù)調(diào)用時(shí)存儲(chǔ)的局部變量和參數(shù)所占用內(nèi)部存儲(chǔ)空間，彈出返回地址，繼續(xù)執(zhí)行調(diào)用函數(shù)語(yǔ)句的下一條語(yǔ)句。

例1 利用遞歸算法計(jì)算正整數(shù)m 的階乘m！。程序代碼如下

（1）每次函數(shù)遞歸調(diào)用，都會(huì)縮小問題的規(guī)模，并且為了防止無(wú)限期的遞歸調(diào)用，必須有結(jié)束遞歸調(diào)用的約束條件。例1 中當(dāng)m 的值為1 時(shí)，ft=1,結(jié)束遞歸調(diào)用，當(dāng)m＞1 時(shí)，發(fā)生遞歸調(diào)用，即在fact(m)函數(shù)中又調(diào)用fact(m-1),下面以3!為例，該函數(shù)遞歸的執(zhí)行過程如圖1所示。

圖1：函數(shù)的遞歸調(diào)用

通過3 次遞歸調(diào)用函數(shù)fact(m)來計(jì)算3 的階乘。第一次調(diào)用fact(3),函數(shù)返回值ft=3* fact(2)，因?yàn)楸磉_(dá)式含有fact(2)，需要調(diào)用函數(shù)本身fact(2)，只是這里函數(shù)參數(shù)已經(jīng)變成2，問題的規(guī)模逐漸縮小，第二次調(diào)用結(jié)束后函數(shù)返回值為ft=2* fact(1)，最后以1為參數(shù)調(diào)用函數(shù)fact(m)時(shí)，函數(shù)返回值為1。最后一次調(diào)用函數(shù)結(jié)束后，返回調(diào)用fact(1)的地址，計(jì)算fact(2)= 2* fact(1)=2*1=2；繼續(xù)返回調(diào)用fact(2)的地址，計(jì)算出fact(3)=3*fact(2)=3*2=6；最后返回到主函數(shù)調(diào)用fact(3)的地址，輸出最終遞歸調(diào)用計(jì)算的結(jié)果。

在整個(gè)函數(shù)遞歸調(diào)用過程中，計(jì)算機(jī)內(nèi)部存儲(chǔ)結(jié)構(gòu)使用棧保存函數(shù)調(diào)用的返回地址和參數(shù)值m，每次調(diào)用結(jié)束時(shí)，都按照棧中存儲(chǔ)本次函數(shù)遞歸調(diào)用的返回地址返回到指定的位置繼續(xù)執(zhí)行，并且通過退棧操作，使得上次調(diào)用的參數(shù)成為新的棧頂繼續(xù)被使用。

（2）函數(shù)遞歸調(diào)用特征就是每次調(diào)用后都必然使得原始問題規(guī)模縮小，并且子問題與原始問題相似，例1 中函數(shù)long fact (int m)的函數(shù)調(diào)用語(yǔ)句“ft=fact(m-1)*m;”就是使求解m 的階乘的問題轉(zhuǎn)化為求m-1 的階乘問題，求解問題規(guī)模不斷的縮小。

（3）遞歸算法實(shí)際求解問題中得到廣泛的應(yīng)用，有些類似的問題需要重復(fù)計(jì)算很多次，就必須使用遞歸算法才能很好的解決，設(shè)計(jì)遞歸算法的一般過程及終止遞歸的約束條件。比如二叉樹遍歷問題、皇后問題、漢諾塔問題等經(jīng)典非數(shù)值的求解，應(yīng)用遞歸算法是解決此類問題的最佳策略。

（4）使用遞歸算法編寫程序，程序代碼簡(jiǎn)潔明了，可讀性強(qiáng)，代碼冗余低，但是函數(shù)遞歸的調(diào)用，特別是數(shù)值計(jì)算類型的遞歸調(diào)用，需要占用大量計(jì)算機(jī)內(nèi)部存儲(chǔ)空間對(duì)函數(shù)多次遞歸調(diào)用的現(xiàn)場(chǎng)保護(hù)及參數(shù)保存，每次調(diào)用時(shí)和調(diào)用結(jié)束返回時(shí)都有入棧和出棧的操作，增加了程序運(yùn)行的時(shí)間長(zhǎng)度，因此遞歸調(diào)用增加了程序運(yùn)行的時(shí)間和空間開銷，降低了程序的執(zhí)行效率。

3 函數(shù)遞歸的適用條件

使用函數(shù)遞歸算法應(yīng)用非常廣泛，正確地使用遞歸算法能夠提高程序的可讀性，降低代碼冗余量，使用不當(dāng)，會(huì)增加程序運(yùn)行的時(shí)間和空間成本。尋找使用遞歸算法的適用場(chǎng)合就顯得很有必要。首先要找出解決問題建立遞歸的關(guān)系，然后理出終止遞歸調(diào)用的約束條件。

能夠使用遞歸解決問題，是否滿足以下關(guān)系：

（1）建立遞歸關(guān)系；

（2）找出遞歸調(diào)用的終止條件；

（3）使用非遞歸算法實(shí)現(xiàn)極為困難，代碼較為繁瑣，可讀性差，而使用遞歸算法編寫的代碼可讀性強(qiáng)，簡(jiǎn)潔明了。

4 函數(shù)遞歸算法的應(yīng)用

4.1 Hanoi塔問題

一板塊上有三根針，即A，B，C。A 針上套有64 個(gè)大小不等的圓盤，大的在下，小的在上，要把這個(gè)64 個(gè)圓盤從A 針移到C針上，每次只能移動(dòng)一個(gè)圓盤，移動(dòng)可以借助B 針進(jìn)行。但在任何時(shí)候，任何針上的圓盤都必須保持大盤在下，小盤在上。

Hanoi 塔問題設(shè)計(jì)算法如下：

設(shè)A 上有n 個(gè)盤子，如果n=1，則將圓盤從A 直接移到C。

如果n=2，則：

（1）將A 上的第一個(gè)圓盤移到B 上。

（2）再將A 上的第二個(gè)圓盤移到C 上。

（3）將B 上的一個(gè)圓盤移到C 上。

如果n=3，則：

（1）將A 上的前2 個(gè)圓盤借助于C 移到B 上，具體過程如下：將A 上的第一個(gè)圓盤移到C 上，再將A 上的第二個(gè)圓盤移到B 上，最后將C 上的一個(gè)圓盤移到B 上，此步驟再重復(fù)n=2 圓盤移動(dòng)全過程。

（2）將A 上的剩下的圓盤移到C 上。

（3）將B 上兩個(gè)圓盤借助于A 移到C 上，具體過程如下：將B 上的第一個(gè)圓盤移到A 上，再將B 上的第二個(gè)圓盤移到C 上，最后將A 上一個(gè)圓盤移到C 上。相當(dāng)于第三步又完全重復(fù)當(dāng)n=2的圓盤移動(dòng)全過程。

從上面分析可以看出，當(dāng)n 大于等于2 時(shí)，圓盤移動(dòng)的過程可以分解為3 個(gè)步驟：

第一，把A 上的n-1 個(gè)圓盤借助于C 移到B 上。

第二、把A 上第n 個(gè)圓盤移到C 上。

第三、把B 上的n-1 個(gè)圓盤借助于A 移到C 上。

第一步和第三步分解為類同的三步，即把n-1 個(gè)圓盤從一個(gè)針上借助于第三個(gè)針移到另一個(gè)針上，這里把n-1 賦值給n，每次移動(dòng)，n 的值遞減一位，并且使用的方法完全一樣，完全滿足函數(shù)遞歸算法設(shè)計(jì)規(guī)則。

主要程序核心代碼如下：

4.2 二叉樹遍歷

二叉樹遍歷分為三種方式，先序遍歷、中序遍歷、后序遍歷，先序遍歷訪問的順序是：根左右，中序遍歷訪問的順序是：左根右，后序遍歷訪問的順序是：左右根。下面以中序遍歷為例，研究二叉樹中序遍歷的遞歸算法，中序遍歷就是首先判斷根結(jié)點(diǎn)的左子結(jié)點(diǎn)是否為空，為空則停止遍歷，不為空將左子結(jié)點(diǎn)作為新的根結(jié)點(diǎn)重新進(jìn)行上述判斷，左子樹遍歷結(jié)束后，然后遍歷訪問該二叉樹的根結(jié)點(diǎn)，并打印根結(jié)點(diǎn)，最后將根結(jié)點(diǎn)的右子結(jié)點(diǎn)作為新的根結(jié)點(diǎn)重新進(jìn)行上述判斷，直至遍歷結(jié)束，到達(dá)每個(gè)結(jié)點(diǎn)時(shí)，打印該結(jié)點(diǎn)的數(shù)據(jù)，就可以得到二叉樹中序遍歷訪問結(jié)果。二叉樹如圖2所示。

圖2：二叉樹

以圖2 為例，二叉樹中序遍歷過程如下：

（1）首先訪問該二叉樹根結(jié)點(diǎn)，此二叉樹根結(jié)點(diǎn)為1；遍歷訪問根結(jié)點(diǎn)1 的左子樹，找到結(jié)點(diǎn)為2；遍歷訪問結(jié)點(diǎn)2 的左子樹，找到結(jié)點(diǎn)4；由于結(jié)點(diǎn)4 沒有左子樹，因此找到結(jié)點(diǎn)4 后，遍歷訪問結(jié)點(diǎn)4 的右子樹，由于結(jié)點(diǎn)4 無(wú)右子樹，因此結(jié)點(diǎn)2 的左子樹遍歷完成，訪問結(jié)點(diǎn)2 并打印該結(jié)點(diǎn)數(shù)據(jù)，遍歷訪問結(jié)點(diǎn)2 的右子樹，找到結(jié)點(diǎn)5，結(jié)點(diǎn)5 沒有左子樹，因此訪問結(jié)點(diǎn)5，又因?yàn)榻Y(jié)點(diǎn)5沒有右子樹，因此結(jié)點(diǎn)1 左子樹遍歷完成。再訪問二叉樹的根結(jié)點(diǎn)1，并打印根結(jié)點(diǎn)1。

（2）訪問結(jié)點(diǎn)1，并遍歷結(jié)點(diǎn)1 的右子樹，找到結(jié)點(diǎn)3，遍歷結(jié)點(diǎn)3的左子樹，找到結(jié)點(diǎn)6，由于結(jié)點(diǎn)6無(wú)左子樹，因此訪問結(jié)點(diǎn)6，又因?yàn)榻Y(jié)點(diǎn)6 沒有右子樹，因此結(jié)點(diǎn)3 左子樹遍歷完成；開始訪問結(jié)點(diǎn)3，并打印該結(jié)點(diǎn)數(shù)據(jù)，并遍歷結(jié)點(diǎn)3 的右子樹，找到結(jié)點(diǎn)7；由于結(jié)點(diǎn)7 無(wú)左子樹，因此訪問結(jié)點(diǎn)7，又因?yàn)榻Y(jié)點(diǎn)7 無(wú)右子樹，因此結(jié)點(diǎn)1 的右子樹遍歷完成，即整個(gè)二叉樹遍歷訪問完成。

此二叉樹的中序遍歷是函數(shù)遞歸算法的典型應(yīng)用，可以用C語(yǔ)言遞歸算法實(shí)現(xiàn)。核心代碼如下：

5 結(jié)論

在C語(yǔ)言程序設(shè)中函數(shù)遞歸算法的應(yīng)用比較普遍，函數(shù)遞歸算法設(shè)計(jì)程序，有利于程序代碼簡(jiǎn)明可讀性性增強(qiáng)，函數(shù)遞歸解決實(shí)際問題要注意問題本身是否適合建立遞歸關(guān)系的條件，如果滿足建立遞歸關(guān)系的條件就可以使用遞歸算法求解，通過經(jīng)典案例的應(yīng)用，對(duì)函數(shù)遞歸算法應(yīng)用執(zhí)行進(jìn)行詳細(xì)的分析，有利于程序設(shè)計(jì)初學(xué)者更好理解遞歸算法的精髓，對(duì)程序開發(fā)者使用遞歸算法解決實(shí)際問題提供借鑒。