汉诺塔的递归实现及盘片目标变化的理解

Question

我正在努力提高自己对用Python解决汉诺塔问题的递归代码的理解。

这段代码：

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")

能正确打印出解决这个谜题所需的移动步骤，所以我之前在Stack Overflow上问过如何理解它是怎么做到的。我得到了这个回答：

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

我唯一不明白的是，在递归过程中，盘子的目标位置（A、B、C）是怎么变化的？第三行 - moveTower: 1 A B 是正确的，我知道盘子应该从A移动到B，但我不明白我们是怎么从A到C（第二行），然后目标变成B的！这很难解释，如果你不明白我说的意思，请问我，但我真的希望能有人帮我理解这个！

这是我理解的代码，针对3个盘子，从=A到=B，使用=C，我写下了我认为递归的样子（这忽略了大部分代码，我只是专注于顶部部分）

def moveTower(3,A, B, C):
    if height >= 1:

        moveTower(2,A,C,B)
            moveTower(1,A, C, B) #so this line of code should be A,B,C but why? as in recursion do we not simply repeat the code again and again? so why would it change if the code initially is ACB why does it change to ABC? 
            moveDisk(A,B,3)
            moveTower(1,C,B,A)

Answer 1

不要把程序里写的代码和实际执行的代码搞混，特别是变量名方面!

def moveTower(3, A, B, C):
    if height >= 1:

        moveTower(2,A,C,B)
            moveTower(1,A, C, B) #so this line of code should be A,B,C but why? as in recursion do we not simply repeat the code again and again? so why would it change if the code initially is ACB why does it change to ABC? 
            moveDisk(A,B,3)
            moveTower(1,C,B,A)

看看这段正确代码的片段，里面的变量名比较短:

def moveTower(height, a, b, c):
    if height >= 1:
        moveTower(height-1, a, c, b)

如果第一次调用是 moveTower(3, 'Peg1', 'Peg2', 'Peg3')，这意味着要把3个盘子（整个塔）从杆1移动到杆2，同时使用杆3作为临时存放的地方。在函数 moveTower 内部，变量 a 被赋值为 'Peg1'，b 被赋值为 'Peg2'，而 c 被赋值为 'Peg3'。

现在开始递归：要把3个盘子从杆1移动到杆2，首先要把两个盘子移动到“辅助杆”，然后用第三根杆作为新的辅助杆:

moveTower(2, a, c, b) # in the first call, a=Peg1, b=Peg2, c=Peg3

这会导致再次调用 moveTower，但这次我们有： a 仍然是 'Peg1'，b 是 'Peg3'，而 c 是 'Peg2'，因为在调用时 c 和 b 的位置互换了。然后又进行了一步递归:

moveTower(1, a, c, b) 

变量名是一样的，但现在它们的值不同了：c 变成了 'Peg2'！所以在下一次调用 moveTower 时，我们有（和第一次调用一样）：a 还是 'Peg1'，b 是 'Peg2' 因为这是第二个参数，而在调用 moveTower 时，第二个参数是 c='Peg2'，而新的 c 从之前的 b 得到 'Peg3'。

希望这能帮到你。如果你用手动计算递归（用笔和纸）并写下每一步哪个变量有什么内容，可能会理解得更好。