4.4 递归可视化
前文探讨了一些能用递归轻松解决的问题。但是，要想象递归的样子或者将递归过程可视化仍然十分困难。
这使得递归难以掌握。本节将探讨一系列使用递归来绘制有趣图案的例子。看着这些图案一点一点地形成，
你会对递归过程有新的认识，从而深刻地理解递归的概念。
我们将使用Python的turtle模块来绘制图案。Python的各个版本都提供turtle模块，它用起来非常简便。
顾名思义，可以用turtle模块创建一只小乌龟（turtle）并让它向前或向后移动，或者左转、右转。小乌龟的
尾巴可以抬起或放下。当尾巴放下时，移动的小乌龟会在其身后画出一条线。若要增加美观度，可以改变小乌
龟尾巴的宽度以及尾尖所蘸墨水的颜色。
让我们通过一个简单的例子来展示小乌龟绘图的过程。使用turtle模块递归地绘制螺旋线，如代码清单4-5
所示。先导入turtle模块，然后创建一个小乌龟对象，同时也会创建用于绘制图案的窗口。接下来定义
drawSpiral函数。这个简单函数的基本情况是，要画的线的长度（参数len）降为0。如果线的长度大于0，
就让小乌龟向前移动len个单位距离，然后向右转90度。递归发生在用缩短后的距离再一次调用drawSpiral
函数时。代码清单4-5在结尾处调用了myWin.exitonclick()函数，这使小乌龟进入等待模式，直到用户在
窗口内再次点击之后，程序清理并退出。
代码清单4-5 用turtle模块递归地绘制螺旋线
from turtle import *
myTurtle = Turtle()
mywin = myTurtle.getscreen()
def drawSpiral(myTurtle, lineLen):
if len > 0:
myTurtle.forward(lineLen)
myTurtle.right(90)
drawSpiral(myTurtle, lineLen-5)
drawSpiral(myTurtle, 100)
mywin.exitonclick()
理解了这个例子的原理，便能用turtle模块绘制漂亮的图案。接下来绘制一棵分形树。分形是数学的一
个分支，它与递归有很多共同点。分形的定义是，不论放大多少倍来观察分形图，它总是有相同的基本形
状。自然界中的分形例子包括海岸线、雪花、山岭，甚至树木和灌木丛。众多自然现象中的分形本质使得
程序员能够用计算机生成看似非常真实的电影画面。下面来生成一棵分形树。
思考如何用分形来描绘一棵树。如前所述，不论放大多少倍，分形图看起来都一样。对于树木来说，
这意味着即使是一根小嫩枝也有和一整棵树一样的形状和特征。借助这一思想，可以把树定义为树干，
其上长着一棵向左生长的子树和一棵向右生长的子树。因此，可以将树的递归定义运用到它的左右子树上。
让我们将上述想法转换成Python代码。代码清单4-6展示了如何用turtle模块绘制分形树。仔细研究
这段代码，会发现第5行和第7行进行了递归调用。第5行在小乌龟向右转了20度之后立刻进行递归调用，
这就是之前提到的右子树。然后，第7行再一次进行递归调用，但这次是在向左转了40度以后。之所以
需要让小乌龟左转40度，是因为它首先需要抵消之前右转的20度，然后再继续左转20度来绘制左子树。同
时注意，每一次进行递归调用时，都从参数branchLen中减去一些，这是为了让递归树越来越小。
第2行的if语句会检查branchLen是否满足基本情况。
代码清单4-6 绘制分形树
def tree(branchLen,t):
if branchLen > 5:
t.forward(branchLen)
t.right(20)
tree(branchLen-10,t)
t.left(40)
tree(branchLen-10,t)
t.right(20)
t.backward(branchLen)
请执行分形树的代码，但在此之前，先想象一下绘制出来的树会是什么样。这棵树是如何开枝散叶的呢？
程序是会同时对称地绘制左右子树，还是会先绘制右子树再绘制左子树？在输入tree函数的代码之后，可以用
下面的代码来绘制一棵树。
drawSpiral(myTurtle, 100)
mywin.exitonclick()
myTurtle.left(90)
myTurtle.up()
myTurtle.backward(350)
myTurtle.down()
myTurtle.color("green")
tree(110,myTurtle)
mywin.exitonclick()
注意，树上的每一个分支点都对应一次递归调用，而且程序先绘制右子树，并一路到其最短的嫩枝，如图
4-7所示。接着，程序一路反向回到树干，以此绘制完右子树，如图4-8所示。然后，开始绘制左子树，但并不
是一直往左延伸到最左端的嫩枝。相反，左子树自己的右子树被完全画好后才会绘制最左端的嫩枝。
图4-7 先绘制右子树
图4-8 分形树的右半部分
这个简单的分形树程序仅仅是一个开始。你会注意到，绘制出来的树看上去并不真实，这是由于自然界并不
如计算机程序一样对称。在本章最后的练习中，你将探索如何绘制出看起来更真实的树。