Tower Of Hanoi - JavaScript - THe Good Parts

Question

我看过SO上关于递归函数的其他问题，也读了回答，但我仍然无法理解算法。

var hanoi = function (disc, src, aux, dst) {

  if (disc > 0) {
    hanoi(disc - 1, src, dst, aux);
   document.write('Move disc ' + disc + ' from ' + src + ' to ' + dst);
    hanoi(disc - 1, aux, src, dst);
  }
}

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

document.write(...)是如何运行的？我的逻辑是第一次运行函数时，disc > 3。然后我们递归调用该函数，跳过下面的所有内容，那么document.write怎么有机会运行呢？

我理解递归（做过基本示例），但我仍然看不到如何得到输出。如果有一种方法可以在可视化环境中运行并查看它的操作，那将非常有帮助。

- Mike Diaz

Answer 1

你可以把将要发生的事情想象成一个调用树（时间从上到下移动）：

你可以把将要发生的事情想象成一个调用树（时间从上到下移动）：

hanoi(3, ...) =>
 |-> hanoi(2, ...) =>
 |    |-> hanoi(1, ...) =>
 |    |    |-> hanoi(0, ...) =>
 |    |    |    \-> (does nothing)
 |    |    |-> document.write(...)
 |    |    |-> hanoi(0, ...) =>
 |    |    |    \-> (does nothing)
 |    |  <-/ [hanoi(1, ...) finished]
 |    |-> document.write(...)
 |    |-> hanoi(1, ...) =>
 |    |    |-> hanoi(0, ...) =>
 |    |    |    \-> (does nothing)
 |    |    |-> document.write(...)
 |    |    |-> hanoi(0, ...) =>
 |    |    |    \-> (does nothing)
 |    |  <-/ [hanoi(1, ...) finished]
 |  <-/ [hanoi(2, ...) finished]
 |-> document.write(...) [halfway done!]
 |-> hanoi(2, ...) =>
 |    \-> [same pattern as the first time, with different data]
 \-> [hanoi(3, ...) finished]

- Ted Hopp

---

+1 我本来也想写同样的话，但你的更易读。我认为关键是要将每个 hanoi() 视为前一个 hanoi() 的子程序，而不是 GOTO。在这种意义上，它确实让 disc 走到了 0，但仍然有三个 hanoi 开放，并且它们将继续运行。就像“安妮会在鲍勃离开后离开，鲍勃会在辛迪离开后离开，辛迪会在道格离开后离开”之类的。 - brymck