汉诺塔问题 Python - 理解递归

Question

我刚开始学习Python，现在正在看一个关于汉诺塔和递归的教程。我以为我理解了递归，直到他们给了我这个例子：

def moveTower(height,fromPole, toPole, withPole):
    if height >= 1:
        moveTower(height-1,fromPole,withPole,toPole)
        moveDisk(fromPole,toPole)
        moveTower(height-1,withPole,toPole,fromPole)
    #print(withPole)

def moveDisk(fp,tp):
    print("moving disk from",fp,"to",tp)


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

这个例子打印出了用3个盘子解决汉诺塔问题的正确步骤： 从A移动盘子到B 从A移动盘子到C 从B移动盘子到C 从A移动盘子到B 从C移动盘子到A 从C移动盘子到B 从A移动盘子到B

我想问的是，它是怎么做到的呢？！能不能帮我看看这些代码，让我明白它是怎么打印出正确的移动步骤的？我主要搞不懂的是fp和tp的值是怎么从A变到B再到C的。抱歉这个问题有点宽泛！任何帮助都非常感谢！

Answer 1

你应该打印每次调用moveTower时的参数，这样可以看到参数的变化。递归通常会通过参数来传递变化。使用序列号可以帮助显示顺序（当然，打印到控制台的顺序也是有序的）。

def seq_nummer():
    num = 0
    while True:
        num += 1
        yield num

seq_num = seq_nummer()

def moveTower(height, fromPole, toPole, withPole):
    print("seq: %d" % seq_num.next())
    print("height: %d, fromPole: %s, toPole: %s, withPole: %s" % (height, fromPole, toPole, withPole))
    if height >= 1:
        moveTower(height-1, fromPole, withPole, toPole)
        moveDisk(fromPole, toPole)
        moveTower(height-1, withPole, toPole, fromPole)

def moveDisk(fp,tp):
    print("moving disk from",fp,"to",tp)

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

Answer 2

这个话题在这里有介绍，不过如果你对递归这个概念不太熟悉，可能会觉得有点难理解。这个算法的工作原理是，首先通过一个临时的柱子，把除了最后一个盘子以外的所有盘子递归地移动走（这其实是一个更小的问题），然后再把最后一个盘子“真正地”移动到目标柱子上，最后再把之前的塔移动回最初的柱子。实际上，依靠递归，底下的盘子被移动到了目标柱子上，而这一步是不能直接完成的，因为那样是无效的移动。在递归调用中，三个柱子的角色会变化，总是有一个空柱子作为临时柱子。想象一下，如果这些柱子不是排成一行，而是围成一个圈，这样理解起来会更容易。与其他问题不同的是，在这里，递归调用是先进行的，然后才是“实际”的移动。

这个问题可以看作是这个问题的重复。

Answer 3

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

把除了一个盘子以外的所有盘子，从起始的柱子移动到中间的柱子，过程中可以使用第三根柱子。

moveDisk(fromPole,toPole)

把最后一个盘子从起始柱子移动到最终柱子。现在最后一个盘子已经放在正确的位置，不需要再移动了。

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

把所有盘子从中间的柱子移动到最终的柱子，如果需要的话，可以使用第一根柱子。

Answer 4

A|
B|
C|321

这是它的工作原理。起始位置是：

A|321
B|
C|

然后用 moveTower(2,fromA,toC, withB) 结果是：

A|3
B| 
C|21

接着，moveDisk(fromA, toB) 的作用是：

A|
B|3
C|21

最后，moveTower(2,fromC, toB) 就结束了这个游戏。

这就是汉诺塔的常见解法：把高度为 h-1 的塔移动到 withPole，然后把最大的盘子移动到 endPole，最后把高度为 h-1 的塔移动到 endPole。

这样做是因为你可以把高度为 h-1 的塔中的每个盘子放在最大的盘子上面。

要执行 moveTower(height-1,w,x)，你可以把所有剩下的盘子放在三个塔中。

所以你会先 moveTower(height-2,y,z)，然后把第二大的盘子移动到它的目的地，再把高度为 height-2 的塔移动一次。

编辑：在 这个链接 中的图示最能说明我想表达的意思（“一图胜千言”）。

如果你知道如何移动一个高度为 height-1 的塔，那就按照你算法中描述的三个步骤来做。moveDisc 是“基本情况”（迈出第一步），而 moveTower 是递归（如何从第 n 步到第 n+1 步）。

Answer 5

在这个简单的例子中，你可以通过使用合适的 print 语句来直观地看到发生了什么，像这样：

def moveTower(height,fromPole, toPole, withPole):
    if height >= 1:
        print( "    "*(3-height), "moveTower:", height, fromPole, toPole )
        moveTower(height-1,fromPole,withPole,toPole)
        moveDisk(fromPole,toPole,height)
        moveTower(height-1,withPole,toPole,fromPole)
    #print(withPole)

def moveDisk(fp,tp,height):
    print("    "*(4-height), "moving disk", "~"*(height), "from",fp,"to",tp)


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

输出结果是：

moveTower: 3 A B
     moveTower: 2 A C
         moveTower: 1 A B
             moving disk ~ from A to B
         moving disk ~~ from A to C
         moveTower: 1 B C
             moving disk ~ from B to C
     moving disk ~~~ from A to B
     moveTower: 2 C B
         moveTower: 1 C A
             moving disk ~ from C to A
         moving disk ~~ from C to B
         moveTower: 1 A B
             moving disk ~ from A to B