10

这是我解释递归的书中的代码。问题是我不明白程序采取的步骤：

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 + "<br />");
        hanoi(disc - 1,aux,src,dst);
    }
};

hanoi(3,"src","aux","dst");

这是输出的读取方式：

Move disc 1 from src to dst
Move disc 2 from src to aux
Move disc 1 from dst to aux
Move disc 3 from src to dst
Move disc 1 from aux to src
Move disc 2 from aux to dst
Move disc 1 from src to dst

有人可以逐步分解吗？这对我很有帮助。

4

2 回答 2

14

河内塔最简单的解决方案可能是这样的：

要将x圆盘从 peg A 移动到 peg C，使用 peg B 作为“辅助” peg：

  1. 使用挂钉 C 作为辅助挂钉，将x-1圆盘从挂钉 A 移到挂钉 B。
  2. 将第x'th 个圆盘从 peg A 移到 peg C（不需要辅助 peg，因为您只移动一个圆盘）。
  3. 将x-1圆盘从挂钉 B 移到挂钉 C，使用挂钉 A 作为辅助挂钉。

请注意，为了移动x光盘，您必须移动x-1光盘。您可以使用相同的功能来移动这些x-1光盘，只需切换哪些钉是源钉、目标钉和辅助钉。这就是使河内之塔成为递归的常见示例的原因，并且这就是您需要在问题中看到的那种模式才能使递归为您工作。当然，它不必是“移动x-1光盘”......它可能是“列出这个子文件夹”之类的东西。树（如带有子文件夹的目录等）是递归的另一个亮点。与其他工作一样，为了完成某个项目的工作，您可能需要对子项目执行相同的工作。

现在，为了进行有用的递归，您需要一个“基本情况”——递归停止的条件。如果你不这样做，代码将永远运行（或者至少直到它耗尽内存或溢出调用堆栈）。这里的基本情况发生在x == 0（因为移动 0 个圆盘意味着你什么都不做，因为if函数的核心）。也可能是 when x == 1，因为那时您不必递归，但是if每次hanoi调用之前的额外内容会增加一些噪音（递归解决方案的主要好处是它的简单性）。无论如何，当 时x == 0，函数不做任何事情就返回。调用它的函数（x == 1有hanoiargs 切换后再次起作用。

流程有点像这样：

hanoi(3, src, aux, dest)
  hanoi(2, src, dest, aux)
    hanoi(1, src, aux, dest)
      hanoi(0, src, dest, aux)        // no op
      print "Move 1 from src to dest"
      hanoi(0, aux, src, dest)        // no op

    print "Move 2 from src to aux"

    hanoi(1, dest, src, aux)
      hanoi(0, dest, aux, src)        // no op
      print "move 1 from dest to aux"
      hanoi(0, src, dest, aux)        // no op

  print "move 3 from src to dest"

  hanoi(2, aux, src, dest)
    hanoi(1, aux, dest, src)
      hanoi(0, aux, src, dest)        // no op
      print "Move 1 from aux to src"
      hanoi(0, dest, aux, src)        // no op

    print "Move 2 from aux to dest"

    hanoi(1, src, aux, dest)
      hanoi(0, src, dest, aux)        // no op
      print "move 1 from src to dest"
      hanoi(0, aux, src, dest)        // no op
于 2011-08-06T01:50:11.690 回答
4

我已经想通了。分解后，代码运行如下：

var write = function(string) {
document.write(string);
}

var i = 0;

var hanoi = function(disc,src,aux,dst) {
    if (disc > 0) {
    hanoi(disc - 1,src,dst,aux);
    write("Move disc " + disc + " from " + src + " to " + dst + "<br />");
    hanoi(disc - 1,aux,src,dst);
    }
};

hanoi(3,"src","aux","dst");

/*
hanoi(3,"src","aux","dst");
    if (disc > 0) {
    hanoi(2,'src','dst','aux');
        if (disc > 0) {
        hanoi(1,'src','aux','dst');
            if (disc > 0) {
            hanoi(0,'src','dst','aux');
                END
            write("Move disc " + 1 + " from " + src + " to " + dst + "<br />");
            hanoi(0,'aux','src','dst');
                END
            }
        write("Move disc " + 2 + " from " + src + " to " + dst + "<br />");
        hanoi(1,'dst','src','aux');
            if (disc > 0) {
            hanoi(0,'src','dst','aux');
                END
            write("Move disc " + 1 + " from " + src + " to " + dst + "<br />");
            hanoi(0,'aux','src','dst');
                END
            }
        }
    write("Move disc " + 3 + " from " + src + " to " + dst + "<br />");
    hanoi(2,'aux','src','dst');
        if (disc > 0) {
        hanoi(1,'aux','dst','src');
            if (disc > 0) {
            hanoi(0,'src','dst','aux');
                END
            write("Move disc " + 1 + " from " + src + " to " + dst + "<br />");
            hanoi(0,'aux','src','dst');
                END
            }
        write("Move disc " + 2 + " from " + src + " to " + dst + "<br />");
        hanoi(1,'src','aux','dst');
            if (disc > 0) {
            hanoi(0,'src','dst','aux');
                END
            write("Move disc " + 1 + " from " + src + " to " + dst + "<br />");
            hanoi(0,'aux','src','dst');
                END
            }
        }
    }
*/

最令人困惑的部分是可视化第一个递归循环的 END。只有当 disc == 0 时，disc == 3 的语句才最终被写入。

于 2011-08-05T06:20:26.120 回答