javascript - 为什么汉诺塔中的 'disc' 值在 'disc' 次调用中不会递减为 0？

Question

我对汉诺塔的递归解决方案感到困惑，它在每次递归调用时减少 disc 参数，而不从 disc 的初始值开始，也不会在之后结束递归光盘通话次数。

在 disc 次调用之后，disc - 1 不应该达到值 0 吗？在这个优雅的魔术中，魔术师的手在哪里？为什么每个新调用似乎都在处理自己的 disc 值而不是原始参数？

function hanoi(disc, src, dst, aux) {
  if (disc === 0) {
    var disk = src.pop();
    dst.push(disk);
  } else {
    hanoi(disc-1, src, aux, dst);
    var disk = src.pop();
    dst.push(disk);
    hanoi(disc-1, aux, dst, src);
  }
}

hanoi(10, [10, 9, 8, 7, 6, 5, 4, 3, 2, 1], [], []);

Answer 1

阶乘是线性递归。汉诺塔是一个双重递归:每个更深的层次每次调用都需要 2 次递归。因此，移动 N 个圆盘总共需要 2^N - 1 次移动。

该算法的内容如下:

如果这是最大的磁盘: 将其移至目标桩；现在我们完成了。

否则: 将下一个圆盘向下移动到第三个钉子上； 将此移动到目标钉； 将下一个磁盘移动到目标桩；

正是这个“否则”部分需要两次调用才能完成一次。

这对你来说有澄清吗？