使用递归理解汉诺塔的机制

Question

我明白了解决汉诺塔的递归算法是干什么的：

例如，如果我们有三个钉子（A、B、C），我们想从 A -> C 移动 3 个圆盘，我们将圆盘 1 和 2 移动到 B，然后移动最大的圆盘 3，挂住 C，然后将我们之前移动的圆盘 1 和 2 移动到 B，移动到 C。该算法用以下方式伪表示：

FUNCTION MoveTower(disk, source, dest, spare):
  IF disk == 0, THEN:
       move disk from source to dest
    ELSE:
       MoveTower(disk - 1, source, spare, dest)   
       move disk from source to dest              
       MoveTower(disk - 1, spare, dest, source)   
  END IF

我调用：MoveTower(3,A,C,B) 会调用 MoveTower(2,A,B,C) 会调用 MoveTower(1,A,C,B) 最终会达到 move A -> B 的基本情况。

这就是我困惑的地方。当到达基本情况时，我们将 A 上的顶部磁盘移动到 B（单次）递归如何移动其他所有内容？ "backing out phase" 如何移动其他圆盘（在本例中是除了最大的所有圆盘到 B）？它不只是移动底壳的顶部圆盘吗？

例如，我知道在达到基本情况后的阶乘函数中，递归 "returns" 传递给上一个调用的值一直传递到上一个调用，直到顶电话。在每个级别，它都在等待其递归返回。

有人可以帮助我了解递归如何在第一个 MoveTower(disk - 1, source, spare, dest) 调用中完成除了达到基本情况之外的任何事情吗？

谢谢

Answer 1

您必须在脑海中想象调用树：

MoveTower 3, from A, to B, using C:
1. MoveTower 2, from A, to C, using B:
   1.1. MoveTower 1, from A, to B, using C:
        1.1.1. Move disk 1 from A to B.
   1.2. Move disk 2 from A to C.
   1.3. MoveTower 1, from B, to C, using A:
        1.3.1. Move disk 1 from B to C.
2. Move disk 3 from A to B.
3. MoveTower 2, from C, to B, using A:
   3.1. MoveTower 1, from C, to A, using B:
        3.1.1. Move disk 1 from C to A.
   3.2. Move disk 2 from C to B.
   3.3. MoveTower 1, from A, to B, using C:
        3.3.1. Move disk 1 from A to B.

现在如果我们只读取 "Move disk" 操作，我们有：

Move disk 1 from A to B.
Move disk 2 from A to C.
Move disk 1 from B to C.
Move disk 3 from A to B.
Move disk 1 from C to A.
Move disk 2 from C to B.
Move disk 1 from A to B.

至于"how it accomplishes anything"，是这样的：

我们必须将 n 个圆盘从 post A 移动到 post B，使用 post C作为暂存。
有两种可能，n为1，或者n大于1。
如果 n 是 1 我们就移动磁盘。
如果 n 大于 1，我们分三步进行：
- 将 n − 1 个磁盘的较小塔从 A 移动到 C，使用 B 作为临时存储。
- 将最下面的圆盘从A移到B。
- 将 n - 1 个磁盘的较小塔从 C 移动到 B，使用 A 作为临时存储。

Answer 2

要有耐心，要精确。

FUNCTION MoveTower(disk, source, dest, spare):
1.  IF disk == 0, THEN:
2.       move disk from source to dest
3.    ELSE:
4.       MoveTower(disk - 1, source, spare, dest)   
5.       move disk from source to dest              
6.       MoveTower(disk - 1, spare, dest, source)   
7.  END IF

想象自己是一台人类计算机，坐在一张漂亮舒适的办公桌前，手上有大量的纸和铅笔。

要调用一个函数，您可以将函数配方复制到一张空白的 sheet 纸上，然后将它放在您面前。

要调用另一个函数，您需要将该函数的配方复制到一张空白的 sheet 纸上，然后将这张 sheet 纸放在您面前的一叠 sheet 纸上.它不与您是否调用相同函数无关，因为您正在使用它的配方复制.

CALL MoveTower(3, A, C, B)
==> MoveTower_recipe{ disk=3, source=A, dest=C, spare=B }
  | 1. IF disk==0, THEN:
     = IF 3   ==0, THEN:
        ....
    3. ELSE:
    4. CALL MoveTower(disk - 1, source, spare, dest) 
       = CALL MoveTower(3-1, A, B, C)
       ==> MoveTower_recipe{ disk=2, source=A, dest=B, spare=C }
         | 1. IF 2 == 0 THEN:
             .....
           3. ELSE:
           4. CALL MoveTower( 1, A, C, B)
               ==> MoveTower_recipe{ disk=1, source=A, dest=C, spare=B }
                 | 1. IF 1 == 0 THEN:
                   3. ELSE:
                   4. CALL MoveTower(0, A, B, C)
                        ==> MoveTower_recipe{ disk=0, source=A, dest=B, spare=C }
                          | 1. IF 0 == 0 THEN:
                            2. ___move disk{0} from source{A} to dest{B}___      (*1)
                            7. END IF
                        <==
                   5. ___move disk{1} from source{A} to dest{C}___               (*2)
                   6. CALL MoveTower( 0, C, B, A)
                      ==>
  .....
  .....

看到了吗？份的MoveTower功能配方层叠彼此重叠，每个副本都保存着自己的函数命名参数的实际值（这里的堆栈在视觉上向下增长，但在你的办公桌上，文件堆会堆积起来）。

您按照纸张顶部 sheet 上的食谱进行操作，在其页边空白处记下您当前在食谱中所处的位置，以及各种命名参数和/或命名内部变量的值（如果有的话）和/或临时未命名值（如 disk - 1）。

当你用完纸的顶部 sheet 时，你将它扔掉，而不是在将它的 return 值（如果有的话）复制到纸的 sheet 之前在顶部，在你进入现在丢弃的食谱副本之前所在的地方。

您还可以注意到您的人机执行的 输入输出指令 ，遵循功能配方（的副本），在另一个 sheet在你这边的纸上，记录你的程序对现实世界的影响（上面标有 (*1)、(*2) 等）。

就是这样。

您的计算状态记录在堆栈中每个食谱副本的边距中。

当您达到基本情况时，您不仅生成了第一条输出指令；您还在您面前堆积了一大堆功能配方的副本，每个副本都有其关联的数据和状态（当前执行点）。

使用递归理解汉诺塔的机制

Understand the mechanics of Tower of Hanoi using recursion

recursion

towers-of-hanoi