前面几节我们研究了几个相对比较容易的问题，有些有趣的图形问题可以在脑子里建立模型，让我们了解递归的过程。这一节开始我们要研究几个用迭代法比较难而用递归比较容易的问题，然后是一个看起来很简单但实际上很难的问题来结束。

河内塔问题

河内塔（汉诺塔的译法比较通行，但不对）问题是法国数学家Edouard Lucas于1883年受一个传说的启示提出的。据说是印度神庙里传授给年轻僧侣的谜题。开始的时候，给他们三个柱子和一摞64个的金盘，每个盘子都比他下面的一个稍小，他们的任务是把64个盘子从一个传递到另一个，有两条规定：一次只能移动一个盘子，不能把大盘子放在小盘子上面。僧侣们非常努力，日夜不休，每秒传递一个盘子，当他们完成工作时，神庙化为灰尘，世界将就此消失。传说是这么说的。

传说有意思吧，不过你不用担心世界末日马上就要到来，因为完成这64个盘子移动，需要2⁶⁴-1=18,446,744,073,709,551,615秒，也就是说需要584,942,417,355年。不怕，没那么快，。

传说有意思吧，不过你不用担心世界末日马上就要到来，因为完成这64个盘子移动，需要2⁶⁴-1=18,446,744,073,709,551,615秒，也就是说需要584,942,417,355年。不怕，没那么快，。

图1河内塔问题的一个中间步骤

问题怎样解决？用递归的话，基点是什么？我们从最下向上思考。假如你有五个盘子，放在1号柱上，如果你知道怎样把4个盘子放到2号柱上，那就可以直接把最下面这个盘子放到3号柱上，然后再把4个盘子从2号柱移动到3号。

但是怎样移动4个盘子呢？假设你知道怎么把3个盘子移动到3号柱，那就有办法把第4个盘子移动到2号柱，然后把3个盘子从3号柱移动到2号柱。

但是你会移动3个盘子吗？那么就把2个盘子先移动2号柱，然后把第3个盘子移动到3号柱，这样行吗？

不要告诉我你不会移动2个盘子啊。

剩下的就是把一个盘子从1号柱移动到3号柱——这就是递归的基点

这里是一个把height个盘子从“起始柱”通过“中间柱”移动盘子到“目标柱”的大纲式描述：

?  把height-1个盘子通过目标柱移动到中间柱上

?  把余下的盘子移动到目标柱上

?  把中间柱上的height-1个盘子通过起始柱移动到目标柱上。

只要遵循这些规则，不管盘子有多少个，都可以通过递归的方式在三步内完成。上面步骤中只少基点。在这个例子中，一个盘子的情形就是基点。另外，向基点的变化是height的减少（1和3）。以下是完成的代码：

defmoveTower(height,fromPole, toPole, withPole):

    if height >= 1:

       moveTower(height-1,fromPole,withPole,toPole)

        moveDisk(fromPole,toPole)

        moveTower(height-1,withPole,toPole,fromPole)

以上的代码简直就是英语的语言描述。算法简化的关键点是利用了2个不同的递归，第一个在第3行，第二个在第5行。第3行我们把起始柱上的盘子只留下一个其他全部移走，下一行把最底下这个直接移动到目标柱上。第5行把刚才移出的的盘子移动到目标柱上最大的盘子上面。基点就是height=0 。这里要记住的重要事情就是：基点返回的地方，就是递归函数最后一次调用的地方

下面是moveDisk函数的实现，非常简单，只做一件事情就是打印一个盘子从一个柱到另一个柱。如果运行一下程序，你会发现这是一个非常有效的谜题答案。

Listing 2

 

defmoveDisk(fp,tp):

    print("moving diskfrom",fp,"to",tp)

以下程序是移动三个盘子的完整代码：

defmoveTower(height,fromPole, toPole, withPole):

    if height >= 1:

        moveTower(height-1,fromPole,withPole,toPole)

        moveDisk(fromPole,toPole)

       moveTower(height-1,withPole,toPole,fromPole)

 

defmoveDisk(fp,tp):

    print("moving diskfrom",fp,"to",tp)

 

moveTower(3,"A","B","C")

运行结果：

在看过moveTower和moveDisk之后，你也许想知道，为什么不用一个数据结构来清晰地跟踪哪个柱子上有哪些盘子。这里有个提示：如果要跟踪的话，需要三个栈对象，每个柱子一个。答案是，python提供了我们需要的栈，但是通过调用栈隐性实现的。（最后这话实在不太明白，没找到相关资料）