姜秋明，王妍婷

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

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

遞歸對于某些問題，是一個十分有用的方法。它可以使某些看來不易解決的問題變得輕而易舉。但遞歸的運用有一定的技巧。我們在程序設(shè)計中不可簡單套用，否則會造成混亂或錯誤，且不易查出錯誤根源。筆者在這方面有過體會，下面以一個實際問題談?wù)勥f歸算法。

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

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

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

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

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

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

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

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

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

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

在程序中，我們了解到在到達出口之前，程序一直在執(zhí)行遞歸算法。遞歸調(diào)用被頻繁使用比我們想象的要多，因為在迷宮里有很多死胡同，它要進去退出來，再重新試探:還有當找到一條路徑后再回溯找其它的路徑。

為了便于分析問題，我們把迷宮簡化為2×3的矩陣，如圖示。

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

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

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

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

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

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

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

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

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