递归算法如何适用于河内塔？ [英] 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 光盘从peg A移到peg C，使用peg B作为auxpeg：

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

1. 将peg A移动 x-1 光盘到peg B，使用peg C作为辅助挂钩。


2. 将 x '光盘从peg A移动到peg C（不需要辅助挂钩，因为你只移动一张光盘）。


3. 将peg B中的 x-1 光盘移动到peg C，使用peg 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 光盘，只需切换哪些挂钩是源，目标和辅助挂钩。这就是使河内之塔成为递归的常见例子的原因，这就是你需要在问题中看到的那种模式，以便让递归适合你。它不一定是移动 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光盘意味着你什么都不做，因为如果围绕功能的肉）。它也可能是 x == 1 ，因为那时你不必递归，但额外的如果在每个 hanoi 调用之前会增加一些噪音（递归解决方案的主要好处是它的简单性）。无论如何，当 x == 0 时，函数返回而不做任何事情。调用它的函数（具有 x == 1 ）现在可以继续执行它的操作 - 在这种情况下，说将光盘1从src移动到dest，然后在args切换的情况下再次调用 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屋！