陳凱

在用計(jì)算機(jī)解決問(wèn)題時(shí)，常會(huì)用到“遞歸”的方法。簡(jiǎn)單來(lái)說(shuō)，遞歸就是程序在執(zhí)行中，某段函數(shù)或過(guò)程調(diào)用到自己。然而，遞歸的方法，似乎和人類日常思考問(wèn)題的方法不太一致，雖然遞歸可以使代碼變得優(yōu)雅簡(jiǎn)潔，但初學(xué)者，卻容易被遞歸弄得云里霧里，就算勉強(qiáng)看得懂別人的代碼，當(dāng)自己運(yùn)用時(shí)，仍然感覺不得要領(lǐng)。

本期，筆者借助兩款游戲，用直觀和互動(dòng)的形式來(lái)展現(xiàn)遞歸的魅力。

Lightbot

第一款游戲叫Lightbot，官網(wǎng)地址是www.lightbot.com，這款游戲是為10歲左右的小朋友準(zhǔn)備的，它既可下載到移動(dòng)設(shè)備運(yùn)行，也可直接在線運(yùn)行。游戲任務(wù)是用盡可能簡(jiǎn)單的命令標(biāo)志（其實(shí)只需要拖拽命令圖標(biāo)，根本不需要敲打鍵盤輸入代碼），來(lái)控制一個(gè)小機(jī)器人點(diǎn)亮藍(lán)色地磚上的燈。

游戲關(guān)卡難度設(shè)置頗為平坦，如為了理解什么是遞歸，先要理解什么是過(guò)程。

由圖1可以看出，機(jī)器人可以使用的命令有“前進(jìn)”“點(diǎn)燈”“左轉(zhuǎn)”“右轉(zhuǎn)”“跳躍”“調(diào)用過(guò)程1（P1）”這六個(gè)，游戲本身并沒有花費(fèi)很多文字告訴人們?yōu)槭裁匆褂谩斑^(guò)程”，然而，因?yàn)橹鞒绦颍∕AIN）只提供了12個(gè)空格，所以就只能將可以重復(fù)做的步驟都填進(jìn)過(guò)程1（PROC1）中，具體解答見圖2。隨著游戲的繼續(xù)，可供填充的空格會(huì)越來(lái)越少，難度也就越來(lái)越高。當(dāng)充分練習(xí)了“過(guò)程”之后，游戲進(jìn)入到“遞歸”的環(huán)節(jié)。

從圖3中可以看出，主程序（MAIN）只有一個(gè)空格，這顯然是有意為之的，因?yàn)檫@就是強(qiáng)迫玩家只能在主程序中調(diào)用其他過(guò)程，而被調(diào)用的過(guò)程“PROC1”中所提供的空格也并不多，所以就只能在被調(diào)用過(guò)程的最后，再調(diào)用自己，于是就形成了遞歸。

如圖4所示，主程序的1個(gè)空格和被調(diào)用過(guò)程的8個(gè)空格全部被填滿，因此，過(guò)程的最后一個(gè)格子必須是調(diào)用過(guò)程自己，所以要填入“P1”，這樣就能點(diǎn)亮所有的燈了。

大家也許會(huì)發(fā)現(xiàn)，在這個(gè)例子中，過(guò)程“PROC1”會(huì)不斷調(diào)用自己，若放到現(xiàn)實(shí)世界中，那個(gè)機(jī)器人一定會(huì)因?yàn)閮?nèi)存被全部占滿而崩潰。因此，在Lightbot的后續(xù)關(guān)卡中，加入了按顏色進(jìn)行判斷以便退出遞歸的圖標(biāo)。

類似的無(wú)退出出口的遞歸的情況，可見如下Python程序代碼：

def proc1（）：

content=raw_input（"Input："） #input string

print content #output string

print content #output string again

proc1（）

proc1（）

以上程序的作用是將用戶輸入的字符串輸出兩次，因?yàn)樵谶^(guò)程最后又調(diào)用了過(guò)程自己，除非強(qiáng)行退出，否則遞歸會(huì)一直繼續(xù)下去。

Lightbot在后續(xù)關(guān)卡中加入了諸如跳板、傳送機(jī)等元素，雖然機(jī)器人跑來(lái)跳去很有趣，但可能也無(wú)法清晰展現(xiàn)出遞歸強(qiáng)大的計(jì)算作用。

Robozzle

還有一款游戲能夠?qū)⑦f歸的計(jì)算能力充分展現(xiàn)出來(lái)，名叫Robozzle。Robozzle游戲的地址是www.robozzle.com，點(diǎn)擊“l(fā)imited version”按鈕，就算不注冊(cè)用戶，也能愉快地挑戰(zhàn)大量設(shè)計(jì)好的謎語(yǔ)，如果注冊(cè)了用戶就能設(shè)計(jì)自己特有的謎語(yǔ)供他人挑戰(zhàn)。游戲任務(wù)是消滅棋盤上的星星，其實(shí)就是拖動(dòng)命令圖標(biāo)和顏色到空格中，指揮一個(gè)“小飛機(jī)”走過(guò)所有標(biāo)注了星星的格子。若按照“easy to hard”的順序玩，“消滅星星”一開始很容易。圖5所示的是某個(gè)用到條件判斷的訓(xùn)練項(xiàng)目。

在圖5中，除了右上角的星星的背景是藍(lán)色的，其他星星的背景都是紅色的，工具欄提供的圖標(biāo)有“前進(jìn)”“左轉(zhuǎn)”“右轉(zhuǎn)”“調(diào)用過(guò)程1（F1）”以及各種顏色的色塊?；疑珘K的作用是：灰色背景上的命令無(wú)論如何都要執(zhí)行，而紅色、藍(lán)色以及其他顏色色塊的作用是只有當(dāng)前“飛機(jī)”所處的背景顏色和當(dāng)前命令的背景顏色一致，才能執(zhí)行該命令，否則就跳到下一個(gè)命令?？梢钥闯觯琑obozzle是用色塊來(lái)進(jìn)行單分支的條件判斷。以上謎語(yǔ)的解答比較簡(jiǎn)單，只要三個(gè)命令就可以完成任務(wù)（此謎語(yǔ)也只提供了三個(gè)空格），分別是一個(gè)灰色背景的前進(jìn)、一個(gè)藍(lán)色背景的右轉(zhuǎn)、一個(gè)灰色背景的F1（調(diào)用自身）（如圖6）。其意義是當(dāng)走到藍(lán)色背景的格子時(shí)右轉(zhuǎn)，其他時(shí)候前進(jìn)，并且在過(guò)程最后調(diào)用自身。

由圖6可以看出，上面的例子也是一個(gè)沒有出口的遞歸。不過(guò)若對(duì)調(diào)用遞歸命令也作條件判斷，就可以實(shí)現(xiàn)一些乍看起來(lái)不可能實(shí)現(xiàn)的任務(wù)。圖7是第330號(hào)謎語(yǔ)，該謎語(yǔ)比先前增加了不少難度（但在大量謎語(yǔ)中還算是容易的）。

此謎語(yǔ)最困擾人的是，右上角處的最后一個(gè)拐彎，因?yàn)榇颂幉]有特別出現(xiàn)不一致的顏色，因此“飛機(jī)”也就不可能在最后的拐彎處根據(jù)條件判斷來(lái)獲得拐彎指令，那么“飛機(jī)”究竟是如何拐彎的？奧妙在于左上角紅色背景的那個(gè)空格。若借助這個(gè)紅色背景的格子放置一個(gè)退出遞歸的標(biāo)志，那么一切就迎刃而解了。

圖8是具體的解決方法，在“F1”過(guò)程中分別放置灰色背景的“F2”“右轉(zhuǎn)”“前進(jìn)”圖標(biāo)，在“F2”過(guò)程中分別放置灰色的“前進(jìn)”、藍(lán)色的“F2”、紅色的“右轉(zhuǎn)”和灰色的“前進(jìn)”圖標(biāo)。為什么要這樣做，藍(lán)色背景的“F2”圖標(biāo)表示只有當(dāng)背景色為藍(lán)色時(shí)才調(diào)用自身，當(dāng)“飛機(jī)”走到紅色的格子時(shí)，此分支結(jié)構(gòu)的條件判斷不再成立，于是就會(huì)執(zhí)行接下來(lái)的紅色“右轉(zhuǎn)”和灰色“前進(jìn)”圖標(biāo)。容易理解的是，紅色“右轉(zhuǎn)”只執(zhí)行了一次，所以“飛機(jī)”頭轉(zhuǎn)向右。那么，為什么在第一次轉(zhuǎn)彎后灰色的“前進(jìn)”還會(huì)被執(zhí)行許多次呢？其實(shí)，剩下的命令都是先前被遞歸打斷而沒有來(lái)得及執(zhí)行的命令。當(dāng)“F2”過(guò)程從所有的遞歸中逐層退出后，最終會(huì)回到“F1”過(guò)程，執(zhí)行剩下的灰色“右轉(zhuǎn)”和灰色“前進(jìn)”兩個(gè)命令。

下面的Python程序，很清晰地展現(xiàn)了與剛才游戲類似的遞歸調(diào)用過(guò)程：

def proc1（）：

content=raw_input（"Input："） #input string

print content #output string

if （content！="0"）：

proc1（）

print content #output string again

proc1（）

該程序運(yùn)行時(shí)，當(dāng)用戶輸入“a”，程序只輸出了一個(gè)“a”，然后就開始調(diào)用自身，剩下的那個(gè)輸出“a”的動(dòng)作被存進(jìn)堆棧中去了，接著用戶可以輸入“b”，程序也只輸出一個(gè)“b”，剩下的那個(gè)輸出“b”的動(dòng)作也被存進(jìn)堆棧中，當(dāng)用戶輸入“0”時(shí)，因條件不滿足，程序不再調(diào)用自身，在退出遞歸的過(guò)程中，執(zhí)行了先前被積壓的動(dòng)作，于是會(huì)倒過(guò)來(lái)輸出“0”“b”“a”。

如果到現(xiàn)在還沒弄明白，不妨對(duì)照以上程序代碼，親手玩一玩“消滅星星”的游戲，當(dāng)謎語(yǔ)解開后，就差不多會(huì)使用遞歸來(lái)寫程序了。隨著水平的提升，游戲的另一種潛力被逐漸揭示出來(lái)，原來(lái)人們除了可以用“飛機(jī)”來(lái)消滅星星，還可以用它來(lái)實(shí)現(xiàn)各種計(jì)算任務(wù)，如二進(jìn)制四則運(yùn)算、斐波那契數(shù)列、分形圖案的繪制等，有興趣的朋友可以挑戰(zhàn)一下。