难以理解 Python 的 Hanoi Towers 递归实现

Difficulty understanding Python's recursive implementation of Hanoi Towers

我找到了一个 Python 代码 online 解决河内塔问题。该代码有效,但我很难理解它。这是:

def hanoi(n, source, helper, target):
    if n > 0:
        # move tower of size n - 1 to helper:
        hanoi(n - 1, source, target, helper)
        # move disk from source peg to target peg
        if source:
            target.append(source.pop())
        # move tower of size n-1 from helper to target
        hanoi(n - 1, helper, source, target)


source = [2, 1]
target = []
helper = []
hanoi(len(source), source, helper, target)

print (source, helper, target)

我对最后一部分有困难:

hanoi(n - 1, helper, source, target)

据我所知,唯一发生的移动是通过 target.append(source.pop()) 行。当我们使用 [2,1] 的简单列表时,在我们将 1 移动到目标列表后,它以某种方式将 1 移动到辅助列表,但是如何???

我的看法,这是程序运行的方式:它到达 n = 0,什么都不做,returns 到 n = 1,将 1 移动到目标,然后它到达我的困难点,并且执行

hanoi(n - 1, helper, source, target)

但由于 n-1 = 0,它什么都不做,然后它应该移动到 n = 2, 源 = [2],助手 = [],目标 = [1]。但是当我在程序上使用 prints 时,我看到在我的难点之后和 n = 2 之前,不知何故函数确实将 1 移动到 helper,并且情况是 source = [2], helper = [1], target = []

它是怎么做到的,即使 n = 0?它有一个条件,只有当 n>0 它才执行?我如何使用指纹查看那一刻发生了什么?

我插入了标准的跟踪打印语句:每次我们进入或退出例程,以及在关键处理节点处。我还加入了缩进以帮助显示调用级别。

还有一个小技巧可以为您说明问题:我为每个堆栈添加了一个字符标签,然后将 n 减一,这样我们就不会移动它们标签。这使您可以在每次调用时准确查看每个角色中的堆栈。

输出应该向您显示每次调用移动的内容,以及递归在所有磁盘改组中发生的位置。当您想到 2 个磁盘时,尝试使用 3 个磁盘。当您开始理解时,将其扩展到 4 个并注释掉一两个跟踪语句——也许只是观察移动。

indent = ""

def hanoi(n, source, helper, target):
    global indent
    indent += "  "
    print (indent, "ENTER", n, source, helper, target)
    if n > 0:
        # move tower of size n - 1 to helper:
        hanoi(n - 1, source, target, helper)
        # move disk from source peg to target peg
        if source:
            print (indent, "MOVE disk", source[-1], "from", source[0], "to", target[0])
            target.append(source.pop())
        # move tower of size n-1 from helper to target
        hanoi(n - 1, helper, source, target)

    print (indent, "LEAVE", n, source, helper, target)
    indent = indent[:-2]


source = ['A', 2, 1]
helper = ['B', ]
target = ['C', ]

print (source, helper, target)
hanoi(len(source)-1, source, helper, target)
print (source, helper, target)

输出:

['A', 2, 1] ['B'] ['C']
   ENTER 2 ['A', 2, 1] ['B'] ['C']
     ENTER 1 ['A', 2, 1] ['C'] ['B']
       ENTER 0 ['A', 2, 1] ['B'] ['C']
       LEAVE 0 ['A', 2, 1] ['B'] ['C']
     MOVE disk 1 from A to B
       ENTER 0 ['C'] ['A', 2] ['B', 1]
       LEAVE 0 ['C'] ['A', 2] ['B', 1]
     LEAVE 1 ['A', 2] ['C'] ['B', 1]
   MOVE disk 2 from A to C
     ENTER 1 ['B', 1] ['A'] ['C', 2]
       ENTER 0 ['B', 1] ['C', 2] ['A']
       LEAVE 0 ['B', 1] ['C', 2] ['A']
     MOVE disk 1 from B to C
       ENTER 0 ['A'] ['B'] ['C', 2, 1]
       LEAVE 0 ['A'] ['B'] ['C', 2, 1]
     LEAVE 1 ['B'] ['A'] ['C', 2, 1]
   LEAVE 2 ['A'] ['B'] ['C', 2, 1]
['A'] ['B'] ['C', 2, 1]