用游戲體驗遞歸

陳凱

在用計算機解決問題時，常會用到“遞歸”的方法。簡單來說，遞歸就是程序在執行中，某段函數或過程調用到自己。然而，遞歸的方法，似乎和人類日常思考問題的方法不太一致，雖然遞歸可以使代碼變得優雅簡潔，但初學者，卻容易被遞歸弄得云里霧里，就算勉強看得懂別人的代碼，當自己運用時，仍然感覺不得要領。

本期，筆者借助兩款游戲，用直觀和互動的形式來展現遞歸的魅力。

Lightbot

第一款游戲叫Lightbot，官網地址是www.lightbot.com，這款游戲是為10歲左右的小朋友準備的，它既可下載到移動設備運行，也可直接在線運行。游戲任務是用盡可能簡單的命令標志（其實只需要拖拽命令圖標，根本不需要敲打鍵盤輸入代碼），來控制一個小機器人點亮藍色地磚上的燈。

游戲關卡難度設置頗為平坦，如為了理解什么是遞歸，先要理解什么是過程。

由圖1可以看出，機器人可以使用的命令有“前進”“點燈”“左轉”“右轉”“跳躍”“調用過程1（P1）”這六個，游戲本身并沒有花費很多文字告訴人們為什么要使用“過程”，然而，因為主程序（MAIN）只提供了12個空格，所以就只能將可以重復做的步驟都填進過程1（PROC1）中，具體解答見圖2。隨著游戲的繼續，可供填充的空格會越來越少，難度也就越來越高。當充分練習了“過程”之后，游戲進入到“遞歸”的環節。

從圖3中可以看出，主程序（MAIN）只有一個空格，這顯然是有意為之的，因為這就是強迫玩家只能在主程序中調用其他過程，而被調用的過程“PROC1”中所提供的空格也并不多，所以就只能在被調用過程的最后，再調用自己，于是就形成了遞歸。

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

大家也許會發現，在這個例子中，過程“PROC1”會不斷調用自己，若放到現實世界中，那個機器人一定會因為內存被全部占滿而崩潰。因此，在Lightbot的后續關卡中，加入了按顏色進行判斷以便退出遞歸的圖標。

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

def proc1（）：

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

print content #output string

print content #output string again

proc1（）

proc1（）

以上程序的作用是將用戶輸入的字符串輸出兩次，因為在過程最后又調用了過程自己，除非強行退出，否則遞歸會一直繼續下去。

Lightbot在后續關卡中加入了諸如跳板、傳送機等元素，雖然機器人跑來跳去很有趣，但可能也無法清晰展現出遞歸強大的計算作用。

Robozzle

還有一款游戲能夠將遞歸的計算能力充分展現出來，名叫Robozzle。Robozzle游戲的地址是www.robozzle.com，點擊“limited version”按鈕，就算不注冊用戶，也能愉快地挑戰大量設計好的謎語，如果注冊了用戶就能設計自己特有的謎語供他人挑戰。游戲任務是消滅棋盤上的星星，其實就是拖動命令圖標和顏色到空格中，指揮一個“小飛機”走過所有標注了星星的格子。若按照“easy to hard”的順序玩，“消滅星星”一開始很容易。圖5所示的是某個用到條件判斷的訓練項目。

在圖5中，除了右上角的星星的背景是藍色的，其他星星的背景都是紅色的，工具欄提供的圖標有“前進”“左轉”“右轉”“調用過程1（F1）”以及各種顏色的色塊。灰色塊的作用是：灰色背景上的命令無論如何都要執行，而紅色、藍色以及其他顏色色塊的作用是只有當前“飛機”所處的背景顏色和當前命令的背景顏色一致，才能執行該命令，否則就跳到下一個命令。可以看出，Robozzle是用色塊來進行單分支的條件判斷。以上謎語的解答比較簡單，只要三個命令就可以完成任務（此謎語也只提供了三個空格），分別是一個灰色背景的前進、一個藍色背景的右轉、一個灰色背景的F1（調用自身）（如圖6）。其意義是當走到藍色背景的格子時右轉，其他時候前進，并且在過程最后調用自身。

由圖6可以看出，上面的例子也是一個沒有出口的遞歸。不過若對調用遞歸命令也作條件判斷，就可以實現一些乍看起來不可能實現的任務。圖7是第330號謎語，該謎語比先前增加了不少難度（但在大量謎語中還算是容易的）。

此謎語最困擾人的是，右上角處的最后一個拐彎，因為此處并沒有特別出現不一致的顏色，因此“飛機”也就不可能在最后的拐彎處根據條件判斷來獲得拐彎指令，那么“飛機”究竟是如何拐彎的？奧妙在于左上角紅色背景的那個空格。若借助這個紅色背景的格子放置一個退出遞歸的標志，那么一切就迎刃而解了。

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

下面的Python程序，很清晰地展現了與剛才游戲類似的遞歸調用過程：

def proc1（）：

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

print content #output string

if （content！="0"）：

proc1（）

print content #output string again

proc1（）

該程序運行時，當用戶輸入“a”，程序只輸出了一個“a”，然后就開始調用自身，剩下的那個輸出“a”的動作被存進堆棧中去了，接著用戶可以輸入“b”，程序也只輸出一個“b”，剩下的那個輸出“b”的動作也被存進堆棧中，當用戶輸入“0”時，因條件不滿足，程序不再調用自身，在退出遞歸的過程中，執行了先前被積壓的動作，于是會倒過來輸出“0”“b”“a”。

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