遞歸算法分析一例

姜秋明，王妍婷

（湖北工業(yè)職業(yè)技術(shù)學(xué)院公共課部，湖北十堰 442000）

所謂遞歸就是過(guò)程（或函數(shù)）的自調(diào)用，這種調(diào)用既可以是直接的，也可以是間接的［1］。

遞歸對(duì)于某些問(wèn)題，是一個(gè)十分有用的方法。它可以使某些看來(lái)不易解決的問(wèn)題變得輕而易舉。但遞歸的運(yùn)用有一定的技巧。我們?cè)诔绦蛟O(shè)計(jì)中不可簡(jiǎn)單套用，否則會(huì)造成混亂或錯(cuò)誤，且不易查出錯(cuò)誤根源。筆者在這方面有過(guò)體會(huì)，下面以一個(gè)實(shí)際問(wèn)題談?wù)勥f歸算法。

問(wèn)題表述:找出從入口經(jīng)過(guò)迷宮到出口的最短路徑。迷宮如圖示，畫斜線的位置不能通行，只能從一個(gè)空白位置走到一個(gè)與之相鄰的空白位置，但不能走重復(fù)路線。

解決這一問(wèn)題可用遞歸算法，用遞歸算法寫出的程序比較簡(jiǎn)短明了。算法描述如下:

1.用一個(gè)矩陣，即二維數(shù)組 maze［i，j］表示迷宮，當(dāng)其值為“1”表示不通行，迷宮之外顯然也不可通行，可預(yù)先設(shè)為“1”。當(dāng)值為“0”，表示可通行。

2.用兩一維數(shù)組記錄可以通行路徑的方格坐標(biāo)（即對(duì)應(yīng)二維數(shù)組下標(biāo)）。

3.建立一個(gè)包函遞歸算法的嘗試程序try（x，y，i:interger）。

（1）占據(jù)入口，把入口二維數(shù)組的兩下標(biāo)傳給兩一維數(shù)組。

（2）向右、左、上、下嘗試，如果數(shù)組 maze［i，j］=0，則占據(jù)它作為一個(gè)新入口。

（3）重復(fù)（1）、（2）直至到達(dá)出口。實(shí)際上這里就是遞歸調(diào)用。每調(diào)用一次就傳給兩一維數(shù)組一對(duì)坐標(biāo)值，這樣當(dāng)?shù)竭_(dá)出口時(shí)，我們就得到所過(guò)路徑的“坐標(biāo)序列”。當(dāng)然，這未必是最短路徑。

4.用一個(gè)值stepnum記錄路徑長(zhǎng)。當(dāng)新生產(chǎn)的路徑比先產(chǎn)生的路徑短時(shí)就要更換它，否則棄之。這樣，當(dāng)所有可能的路徑搜索完后，“坐標(biāo)序列”記錄的就是最短路徑。

下面給出用passcal語(yǔ)言寫的嘗試程序try（x，y，i:integer），并分析遞歸調(diào)用過(guò)程［2］。

在程序中，我們了解到在到達(dá)出口之前，程序一直在執(zhí)行遞歸算法。遞歸調(diào)用被頻繁使用比我們想象的要多，因?yàn)樵诿詫m里有很多死胡同，它要進(jìn)去退出來(lái)，再重新試探:還有當(dāng)找到一條路徑后再回溯找其它的路徑。

為了便于分析問(wèn)題，我們把迷宮簡(jiǎn)化為2×3的矩陣，如圖示。

在這里程序度試探到出口后，又回溯到入口，并釋放所有被占據(jù)的點(diǎn)（入口由主程序釋放），在比較復(fù)雜的迷宮中，回溯時(shí)會(huì)拐到另一路徑上，然后再回溯，如此類推可以找到所有路徑［3］。

通過(guò)對(duì)這個(gè)簡(jiǎn)單情況的程序跟蹤，我們了解了遞歸調(diào)用的細(xì)節(jié)，做到心中有數(shù)，使我們?cè)谡{(diào)試程序時(shí)不致因?yàn)檫f歸是“暗箱”而不知如何修改參數(shù)或程序。在這個(gè)遞歸算法程序中，應(yīng)注意以下問(wèn)題:

（1）程序在調(diào)用自身或回溯時(shí)，變量i值的變化。內(nèi)層調(diào)用的變量i是不會(huì)傳給外層的，更不會(huì)通過(guò)外層傳給其他內(nèi)層調(diào)用程序。其他數(shù)據(jù)也是如此。

（2）在get－path過(guò)程中，慎用變量i，以免引起混亂。i既是調(diào)用層次記錄，也是路徑長(zhǎng)記錄，變化相當(dāng)頻繁而復(fù)雜。

（3）釋放被占據(jù)點(diǎn)的時(shí)機(jī)要恰當(dāng)。如果提前釋放，會(huì)造成走重復(fù)路線，甚至死循環(huán)。如果滯后釋放或不釋放，可能會(huì)得不到路徑或得不到所需的最短路徑。

遞歸算法還應(yīng)用于很多方面;它的優(yōu)勢(shì)之處是令人信服的。如果要用等價(jià)的程序?qū)⒑芊爆嵡也灰卓炊?。希望這一例遞歸算法分析能起到拋磚引玉的作用，使我們對(duì)它的運(yùn)用更上一層次。

［1］N·沃思.算法+數(shù)據(jù)結(jié)構(gòu)=程序［M］.北京:科學(xué)出版社，1984:164.

［2］李永新 .漢諾塔問(wèn)題的非遞歸算法實(shí)現(xiàn)［J］.湖州師范學(xué)院學(xué)報(bào)，2008（6）:43－47.

［3］孟 林，尹德輝.二叉樹遍歷遞歸算法非遞歸討論［J］.福建電腦，2004（6）:30－31.