河内之塔:递归算法 [英] Tower of Hanoi: Recursive Algorithm

问题描述

尽管我对理解递归没有任何问题，但是我似乎无法将自己的头围在河内塔问题的递归解决方案上.这是来自维基百科的代码:

Although I have no problem whatsoever understanding recursion, I can't seem to wrap my head around the recursive solution to the Tower of Hanoi problem. Here is the code from 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;

我了解基本情况以及将问题分解成小块直到可以移动单个磁盘的概念.但是，我无法弄清楚在非基本情况下这两个递归调用是如何一起工作的.也许有人可以帮助我?谢谢.

I understand the base case and the concept of breaking the problem into smaller pieces until you are able to move a single disk. However, I can't figure out how the two recursive calls in the non-base case work together. Perhaps someone can help me out? Thanks.

推荐答案

实际上，部分从何处您采用的代码也提供了解释:

Actually, the section from where you took that code offers an explanation as well:

要将n张光盘从钉A移到钉C:

To move n discs from peg A to peg C:

1. 将n−1个光盘从A移动到B.这使#n光盘独自留在钉A上
2. 将光盘#n从A移到C
3. 将n-1个光盘从B移到C，因此它们位于#n光盘上

很明显，您首先必须删除 n -1个光盘才能访问第 n 个光盘.而且您必须首先将它们移动到另一个钉子，而不是想要整个塔楼出现的地方.

It's pretty clear that you first have to remove n − 1 discs to get access to the nth one. And that you have to move them first to another peg than where you want the full tower to appear.

帖子中的代码除了光盘数量外，还包含三个参数: source 钉， destination 钉和 temporary 钉可以在其间存储哪些光盘(每个大小 n − 1的光盘都适合).

The code in your post has three arguments, besides the number of discs: A source peg, a destination peg and a temporary peg on which discs can be stored in between (where every disc with size n − 1 fits).

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

The recursion happens actually twice, there, once before the writeln, once after. The one before the writeln will move n − 1 discs onto the temporary peg, using the destination peg as temporary storage (the arguments in the recursive call are in different order). After that, the remaining disc will be moved to the destination peg and afterwards the second recursion compeltes the moving of the entire tower, by moving the n − 1 tower from the temp peg to the destination peg, above disc n.

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