5

目前我正在阅读 Douglas Crockford 的书，河内塔楼功能有点超出我的想象。即使将内容记录到控制台，我也无法真正理解发生了什么。这是我添加的功能：

var hanoi = function (disc, src, aux, dst) {
  console.log(disc);
  console.log(src, dst);    
  if (disc > 0) {
    hanoi(disc - 1, src, dst, aux);
    console.log('Move disc ' + disc + ' from ' + src + ' to ' + dst);
    hanoi(disc - 1, aux, src, dst);
  }
}

hanoi(3, 'Src', 'Aux', 'Dst');

这导致以下结果：

3
Src Dst
2
Src Aux
1
Src Dst
0
Src Aux
将光盘 1 从 Src 移动到 Dst
0
Aux Dst
将光盘 2 从 Src 移动到 Aux
1
Dst Aux
0
Dst Src
将光盘 1 从 Dst 移动到 Aux
0
Src Aux
将光盘 3 从 Src 移动到 Dst
2
Aux Dst
1
Aux Src
0
Aux Dst
将光盘 1 从 Aux 移动到 Src
0
Dst Src
将光盘 2 从 Aux 移动到 Dst
1
Src Dst
0
Src Aux
将光盘 1 从 Src 移动到 Dst
0
辅助目的地

我很早就迷路了。在结果的第 6 行，它如何从 Src Aux 回到 Src Dst？

当函数仅使用“disc - 1”调用自身时，一旦达到 0，磁盘数量如何再次增加？

4

2 回答 2

9

之所以会产生混淆，是因为输出的文本表示并不是理解递归的最佳方式。光盘的数量并没有“增加”，而是hanoi(1)继续运行一次hanoi(0)。

我在JSBin创建了一个修改过的示例创建了一个修改后的示例，它以（有点）更漂亮的方式打印输出，带有空格。只有“移动”实际上做任何事情，其余的行只是递归调用以解决较小的子问题，以便以后解决整个问题。

您可能还想看看这个以图形方式显示算法如何工作的Java 小程序——这可能更容易理解。

于 2010-09-18T16:10:22.540 回答
5

河内塔是递归如何简化给定问题的一个很好的例子。想法如下：您必须将 N 个磁盘从源堆栈移动到目标堆栈，一次一个磁盘，并且永远不能将较大的磁盘放在较小的磁盘上。您可以使用辅助堆栈。假设 N = 10。你不知道如何解决它。但是您可以使问题更简单（您希望）： 

move 9 disks to the auxiliary stack,  
move the remaining (and largest!) disk to the destination stack, and  
move the 9 disks from the auxiliary stack to the destination stack

同样，您不知道如何移动 9 个磁盘堆栈，但这也没有问题： 

move 8 disks from the auxiliary stack to the source stack,  
move the remaining disk to the destination stack (there are 2 disks now), and  
move the 8 disks from the source stack to the destination stack

重复此操作，直到您必须移动的堆栈只有 1 个磁盘大。

关于再次上升的磁盘数量：你对N-1个磁盘递归调用函数，在函数中分配给N。这个N只存在到函数结束，并返回到上一级。然后你再次得到 N 的旧值。

于 2010-09-18T16:11:51.087 回答