解释这个河内塔解决方案（写在python）

Question

我正在尝试理解河内塔问题的这个特殊解决方案。这是一个递归解决方案。

A = [5, 4, 3, 2, 1]
B = []
C = []

def move(n, source, target, auxiliary, frm):
print('n here : ', n)
if n > 0:
    print('frm : ', frm, n)

    # move n - 1 disks from source to auxiliary, so they are out of the way
    move(n - 1, source, auxiliary, target, '1')

    # move the nth disk from source to target
    target.append(source.pop())

    print('n:', n)

    # Display our progress
    print(source, target, auxiliary, '##############', sep = '\n')

    # move the n - 1 disks that we left on auxiliary onto target
    move(n - 1, auxiliary, target, source, '2')

# initiate call from source A to target C with auxiliary B
move(5, A, C, B, '0')

你可以在这里看到 https://repl.it/JUzY/0

打印第一行#########后，n = 0的值变为2，这是怎么发生的？我错过了一些递归的概念吗？帮助我理解这一点。

Answer 1

您需要了解范围。你说 "the value of n = 0, but suddenly it becomes 2"。但是"n"不止一个，因为n的scope就是method。每次调用 move 时，该方法调用都有自己的 n 实例和自己的值。

在脚本的底部，您调用 move(5, A, C, B, '0')。在该调用中，n == 5。要做的第一件事是调用 move(n - 1, source, auxiliary, target, '1')。在那个调用中，n == 4。但是当它最终returns时，原来函数调用中的n仍然是5.

了解递归如何工作的一个好方法是使用纸张手动执行程序。我将使用 Post-It note 进行函数调用，并使用 notebook 进行输出。你也有你的 "model"，以列表 A,B,C 的形式。由于元素四处移动，您可以用纸片或拼字游戏块来表示这些元素。

从首字母 move(4, A, C, B, '0') 开始。（我从 4 开始，因为步数增长很快）。由于我们是调用一个函数，所以取一个新的post-it来表示函数调用，并在上面写上：

n = 4
source = A
target = C
auxiliary = B
frm = '0'

现在按照 move 的代码进行操作。在这个上面写任何 print 输出。

当您接到 move(n - 1, source, auxiliary, target, '1') 的电话时，请在 post-it 上记下您所在的行号，然后获取一个新的 post-it，并写入其中的值：

n = 4     (because 4 - 1)
source = A
target = B  (caller's auxiliary)
auxiliary = C (caller's target)
frm = '1'

将这个放在之前的 post 之上。被掩盖的 post- 它被再次揭露之前，您不得查看它。继续这样做，你最终会得到一堆五个 post-its。

第五个post-它有n = 0。现在，当您单步执行它的代码时，因为它以 if n > 0: 开头，所以会立即调用 returns。这个函数调用结束了，把那个post-it撕了扔掉。 n等post中的值对其他post-中的没有影响。

您记下了所在的行号，因此继续从该行手动执行代码。您将产生一些输出，然后再次调用 move——也使用 post-its 进行此移动，再次覆盖当前的 post-it 并增加您的堆栈，直到您进行调用使用 n == 0 并且可以从堆栈中删除一个项目。

如果你继续这样做，你会看到堆栈增长和收缩几次，你会到达原来的 post-它一次，打印它，然后再次增长堆栈，然后到达原来post-再说一遍，终于写完了。

post 的堆栈 - 它指出的是程序运行时的 执行堆栈 的精确模型。当您看到堆栈跟踪（即使是非递归程序）时，这就是它们所代表的。每个 post-它是一个 堆栈帧 ，局部变量的范围仅限于该堆栈帧。

Hanoi的递归解可以用英文表示为：

要移动大小为零的堆栈，什么也不做
通过辅助将更大的堆栈从 src 移动到目标：
- 首先将n-1个圆盘从src移动到辅助（让他们离开）
  - 按照我们这样做的方式来做。
- 然后将显示的光盘移动到目的地
- 然后将n-1个圆盘从辅助移动到目标，使用src作为备用挂钩
  - 像我们这样做一样

解释这个河内塔解决方案（写在python）

Explain this Towers of Hanoi solution (written in python)

python-3.x

recursion

towers-of-hanoi