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

Question

我找到了一个 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 它才执行？我如何使用指纹查看那一刻发生了什么？

Answer 1

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

还有一个小技巧可以为您说明问题：我为每个堆栈添加了一个字符标签，然后将 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]

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

Difficulty understanding Python's recursive implementation of Hanoi Towers

python

python-3.x

recursion

towers-of-hanoi