Crockford的河内功能(来自"The Good Parts")

Question

目前我正在阅读道格拉斯·克罗克福德(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
从Src移动光盘3至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
Aux Dst

而且我很早就输了.在结果的第6行,它怎么能从Src Aux回到Src Dst？

一旦它达到0,当该功能仅使用"disc-1"调用自身时,光盘的数量怎么能再次上升？

Answer 1

产生混淆是因为输出的文本表示不是理解递归的最佳方式.光盘的数量并没有"上升",而是hanoi(1)一旦hanoi(0)完成就继续运行.

我在JSBin上创建了一个修改过的示例,它以一种(有些)更漂亮的方式用空格打印输出.只有"移动"实际上做了什么,其余的行只是递归调用,以解决较小的子问题,以便以后解决整个问题.

您可能还想看看这个Java小程序,它以图形方式显示算法的工作原理 - 这可能更容易理解.

Answer 2

河内的塔是递归如何简化特定问题的一个很好的例子.这个想法如下:您必须将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的旧值.