javascript - 克罗克福德的河内函数(来自 “The Good Parts”)

This question already has answers here:

How does recursive algorithm work for Towers of Hanoi?

(2个答案)


6年前关闭。




目前，我正在阅读道格拉斯·克罗克福德(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');

结果如下:



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

当该功能仅使用“disc-1”调用自身时，光盘数量达到0后又如何增加？

最佳答案

由于输出的文本表示不是理解递归的最佳方法，所以会造成困惑。光盘的数量不是“上升”的，而是hanoi(1)在hanoi(0)完成后继续运行。

我在JSBin创建了一个修改后的示例，该示例以(某种)更漂亮的方式用空格打印输出。只有“ Action ”实际上可以做任何事情，其余各行只是递归调用，以解决较小的子问题，以便以后解决整个问题。

您可能还想看看这个Java applet，以图形方式显示算法的工作原理-这可能更容易理解。