recursion - 汉诺塔 : Recursive Algorithm

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还提供了解释:

To move n discs from peg A to peg C:

1. move n−1 discs from A to B. This leaves disc #n alone on peg A
2. move disc #n from A to C
3. move n−1 discs from B to C so they sit on disc #n

很明显，您首先必须删除 n - 1 张光盘才能访问第 n 光盘。而且你必须先将它们移动到另一个钉子上，而不是你希望整个塔出现的位置。

除了光盘数量之外，您帖子中的代码还包含三个参数:源钉、目的地钉和临时钉其间可以存储哪些光盘(每个大小为 n - 1 的光盘都适合)。

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