用游戏体验递归

陈凯

在用计算机解决问题时，常会用到“递归”的方法。简单来说，递归就是程序在执行中，某段函数或过程调用到自己。然而，递归的方法，似乎和人类日常思考问题的方法不太一致，虽然递归可以使代码变得优雅简洁，但初学者，却容易被递归弄得云里雾里，就算勉强看得懂别人的代码，当自己运用时，仍然感觉不得要领。

本期，笔者借助两款游戏，用直观和互动的形式来展现递归的魅力。

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”。

如果到现在还没弄明白，不妨对照以上程序代码，亲手玩一玩“消灭星星”的游戏，当谜语解开后，就差不多会使用递归来写程序了。随着水平的提升，游戏的另一种潜力被逐渐揭示出来，原来人们除了可以用“飞机”来消灭星星，还可以用它来实现各种计算任务，如二进制四则运算、斐波那契数列、分形图案的绘制等，有兴趣的朋友可以挑战一下。