汉诺塔:递归算法

Question

虽然我对递归的理解没有任何问题，但我似乎不能理解汉诺塔问题的递归解决方案。以下是来自Wikipedia的代码

procedure Hanoi(n: integer; source, dest, by: char);
Begin
    if (n=1) then
        writeln('Move the plate from ', source, ' to ', dest)
    else begin
        Hanoi(n-1, source, by, dest);
        writeln('Move the plate from ', source, ' to ', dest);
        Hanoi(n-1, by, dest, source);
    end;
End;

我理解基本情况和将问题分解为较小部分的概念，直到您能够移动单个磁盘。但是，我不知道在非基本情况下这两个递归调用是如何协同工作的。也许有人能帮我一下？谢谢。

Answer 1

实际上，section from where you took that code也提供了一个解释：

将n个磁盘从挂接A移动到挂接C：

1. 将n个磁盘从A移动到B。这会使磁盘#n单独存在于peg A上，并将磁盘#n从A移动到C。
2. 将n个磁盘从B移动到C，以便它们位于磁盘#n

上。

很明显，要访问_n_th one，首先必须取出n张−1光盘。你必须先把它们移到另一个柱子上，而不是你想让整个塔出现的地方。

你帖子中的代码有三个参数，除了光盘的数量:一个源peg，一个目标peg和一个临时的peg，可以在其间存储光盘(其中每个大小为n−1的光盘都适合)。

递归实际上发生了两次，一次在writeln之前，一次在之后。writeln之前的一个将n个−1磁盘移动到临时peg上，使用目标peg作为临时存储(递归调用中的参数顺序不同)。在此之后，剩余的圆盘将被移动到目的地桩，然后第二次递归通过将n个−1塔从临时桩移动到盘n上方的目的地桩来强制整个塔的移动。

Answer 2

一年前，我上了一门函数式编程课程，画了这个算法的插图。希望它能帮上忙！

(0)  _|_         |          |
    __|__        |          |
   ___|___       |          |
  ____|____  ____|____  ____|____

(1.1) |          |          |
    __|__        |          |
   ___|___      _|_         |
  ____|____  ____|____  ____|____ (A -> B)

(1.2) |          |          |
      |          |          |
   ___|___      _|_       __|__
  ____|____  ____|____  ____|____ (A -> C)

(1.3) |          |          |
      |          |         _|_
   ___|___       |        __|__
  ____|____  ____|____  ____|____ (B -> C)



(2.1) |          |          |
      |          |         _|_
      |       ___|___     __|__
  ____|____  ____|____  ____|____ (A -> B)



(3.1) |          |          |
      |          |          |
     _|_      ___|___     __|__
  ____|____  ____|____  ____|____ (C -> A)

(3.2) |          |          |
      |        __|__        |
     _|_      ___|___       |
  ____|____  ____|____  ____|____ (C -> B)

(3.3) |         _|_         |
      |        __|__        |
      |       ___|___       |
  ____|____  ____|____  ____|____ (A -> B)

3环问题已拆分为2个2环问题(1.x和3.x)

Answer 3

http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html对河内递归实现有一个很好的解释。

总结一下，如果你想把底部的盘子从A移动到B，你首先必须把上面所有的小盘子从A移动到C。第二个递归调用是在你的底座把一个大的盘子从A移动到B之后，把你移动到C的盘子移回B上。