河内塔的递归算法如何工作? [英] How does recursive algorithm work for Towers of Hanoi?

问题描述

这是我解释递归的一本书中的代码.问题是我不明白程序采取的步骤:

This is code from a book I have explaining recursion. The problem is that I don't understand the steps taken by the program:

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

有人可以逐步分解吗?这对我很有帮助.

Can someone break this down step by step? It would be very helpful to me.

推荐答案

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

Probably the simplest solution to the Towers of Hanoi works like this:

要将 x 个光盘从挂钉 A 移动到挂钉 C，使用挂钉 B 作为辅助"挂钉:

To move x discs from peg A to peg C, using peg B as an "aux" peg:

1. 将 x-1 个光盘从挂钉 A 移动到挂钉 B，使用挂钉 C 作为辅助挂钉.
2. 将第 x 个光盘从挂钉 A 移动到挂钉 C(不需要辅助挂钉，因为您只移动了一张光盘).
3. 将 x-1 光盘从挂钩 B 移动到挂钩 C，使用挂钩 A 作为辅助挂钩.

1. Move x-1 discs from peg A to peg B, using peg C as the aux peg.
2. Move the x'th disc from peg A to peg C (no aux peg needed, cause you're only moving one disc).
3. Move the x-1 discs from peg B to peg C, using peg A as the aux peg.

请注意，要移动x 个光盘，您必须移动x-1 个光盘.您可以使用相同的功能来移动那些 x-1 光盘，只需切换哪个挂钩是源、目标和辅助挂钩.这就是使 Towers of Hanoi 成为递归的常见示例的原因，这就是您需要在问题中看到的那种模式，以便让递归为您工作.它不一定是移动 x-1 光盘"，当然......它可以是列出这个子文件夹".树(如带有子文件夹等的目录)是递归的另一个亮点.与其他工作一样，为了完成某个项目的工作，您可能需要对子项目执行相同的工作.

Note that in order to move x discs, you have to move x-1 discs. You can just use the same function to move those x-1 discs, and just switch which pegs are the source, dest, and aux pegs. That's what makes Towers of Hanoi such a common example of recursion, and that's the kind of pattern you need to see in a problem in order to make recursion work for you. It need not be "move x-1 discs", of course...it could be something like "list this subfolder". Trees (like a directory with subfolders and such) are another place where recursion shines. As do other jobs where in order to do the job on an item, you may need to do the same job on sub-items.

现在，为了获得有用的递归，您需要一个基本情况"——递归停止的条件.如果不这样做，代码将永远运行(或至少直到它耗尽内存或溢出调用堆栈).这里的基本情况发生在 x == 0 时(因为移动 0 个光盘意味着你什么都不做，因为 if 围绕着函数的核心).也可能是 x == 1 时，因为那时您不必递归，但是在每个 hanoi 调用之前额外的 if 会添加一些噪音(递归解决方案的主要好处是它的简单性).无论如何，当 x == 0 时，函数不做任何事情就返回.调用它的函数(它有 x == 1)现在可以继续做它的事情——在这种情况下，说将光盘 1 从 src 移动到 dest"，然后调用 hanoi 函数再次切换，参数切换.

Now, in order to have useful recursion, you need a "base case" -- a condition where the recursion will stop. If you don't, the code will run forever (or at least til it runs out of memory or overflows the call stack). The base case here occurs when x == 0 (since moving 0 discs means you do nothing, due to the if around the meat of the function). It could also be when x == 1, as then you don't have to recurse, but the extra if before each hanoi call would add a bit of noise (and the main benefit to a recursive solution is its simplicity). Anyway, when x == 0, the function returns without doing anything. The function that called it (which had x == 1) now gets to continue doing its thing -- in this case, saying "move disc 1 from src to dest", and then calling the hanoi function again with the args switched.

流程有点像这样:

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

这篇关于河内塔的递归算法如何工作?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！