河内 Python 塔 - 理解递归

Towers of Hanoi Python - understanding recursion

提问by heather

I'm completely new to Python and I am currently going over a tutorial about The Towers of Hanoi and recursion. I thought that I understood recursion until they gave this example:

我对 Python 完全陌生，我目前正在阅读有关河内塔和递归的教程。我以为我理解递归，直到他们给出这个例子：

def moveTower(height,fromPole, toPole, withPole):
    if height >= 1:
        moveTower(height-1,fromPole,withPole,toPole)
        moveDisk(fromPole,toPole)
        moveTower(height-1,withPole,toPole,fromPole)
    #print(withPole)

def moveDisk(fp,tp):
    print("moving disk from",fp,"to",tp)


moveTower(3,"A","B","C")

which prints the correct moves for solving the towers of hanoi problem with 3 discs: moving disk from A to B moving disk from A to C moving disk from B to C moving disk from A to B moving disk from C to A moving disk from C to B moving disk from A to B

用 3 个圆盘打印解决河内塔问题的正确动作： 将圆盘从 A 移到 B 将圆盘从 A 移到 C 将圆盘从 B 移到 C 将圆盘从 A 移到 B 将圆盘从 C 移到 A 将圆盘从 C to B 将磁盘从 A 移到 B

My question is, how does it do so?! could someone go over the lines of code so that I understand how it prints the correct moves? I'm mainly confused with how the value of fpand tpcan change from Ato Bto C. Sorry if this is bit of a broad question! Any help would be greatly appreciated!

我的问题是，它是如何做到的？！有人可以检查代码行，以便我了解它如何打印正确的动作吗？我主要是混淆怎样的价值fp，并tp可以从改变A到B到C。对不起，如果这是一个广泛的问题！任何帮助将不胜感激！

回答by Codor

The topic is covered here, however the recursive approach can be confusing if one is not familiar with the concept. The algorithm works by first recursively moving all but the last disc (a smaller problem instance) via the cache peg away, then "actually" moving the last disk to the destination peg and then moving the tower to the initial peg. In effect, relying on the recursion, the disk at the bottom is moved to the destination peg, which is impossible to do directly as is is no valid move. In the recursive call, the three pegs change the roles such that always an empty peg becomes the cache. This is understood best if you imagine the pegs not to be arranged in the line but in a circle. Unlike other problems, here the recursive call comes first and then the "actual" movement is done.

此处涵盖了该主题，但是如果不熟悉该概念，递归方法可能会令人困惑。该算法的工作原理是首先通过缓存钉递归地移动除最后一个磁盘（较小的问题实例）之外的所有磁盘，然后“实际上”将最后一个磁盘移动到目标钉，然后将塔移动到初始钉。实际上，依靠递归，底部的磁盘被移动到目标挂钩，这是不可能直接做到的，因为这是无效的移动。在递归调用中，三个 peg 改变了角色，使得总是一个空的 peg 成为缓存。如果您想像钉子不是排列在一条线上而是排列成一个圆圈，这将是最好的理解。与其他问题不同的是，这里首先进行递归调用，然后完成“实际”移动。

The question can be seen as a duplicate of thisquestion.

这个问题可以看作是这个问题的重复。

回答by fredtantini

here is what it does. The starting position is:

这是它的作用。起始位置是：

A|321
B|
C|

then with moveTower(2,fromA,toC, withB)the result is:

然后moveTower(2,fromA,toC, withB)结果是：

A|3
B| 
C|21

then, moveDisk(fromA, toB)does

那么，moveDisk(fromA, toB)是否

A|
B|3
C|21

and finally moveTower(2,fromC, toB)ends the game

并最终moveTower(2,fromC, toB)结束游戏

A|
B|
C|321

That is the usual solution for Hanoi: move the tower of height h-1to the withPole, move the largest disc to the endPoleand move tower of height h-1to the endPole.

这是河内通常的解决方案：将高塔移动h-1到withPole，将最大的圆盘endPole移动到并将高塔移动h-1到endPole。

That works because you can move each disc of the tower of height h-1on the largest disc.

这是有效的，因为您可以h-1在最大的圆盘上移动高度塔的每个圆盘。

To do moveTower(height-1,w,x)you are allowed to place all the remaining disc in all the 3 towers.

要做到这一点，moveTower(height-1,w,x)您可以将所有剩余的圆盘放置在所有 3 个塔中。

So you will moveTower(height-2,y,z)then move the 2nd largest disc to its destination, and move the tower height-2 again.

因此，您将moveTower(height-2,y,z)然后将第二大圆盘移动到其目的地，并再次移动高度为 2 的塔。

Edit: The diagram in this linkbest describs what I am trying to say ("A picture is worth a thousand words").

编辑：此链接中的图表最好地描述了我想说的内容（“一张图片值得一千字”）。

If you know of to move a tower of height-1then, just do the 3 steps described in your algorithm. moveDiscis the "base case" (climb the first step), moveTower is the recursion (how to go from step nto n+1).

如果您知道要移动塔height-1，只需执行算法中描述的 3 个步骤。moveDisc是“基本情况”（爬上第一步）， moveTower 是递归（如何从 stepn到n+1）。

回答by pentadecagon

In this simple case you can just visualize what happens by using appropriate prints, like this:

在这个简单的情况下，您可以通过使用适当的prints来可视化发生的情况，如下所示：

def moveTower(height,fromPole, toPole, withPole):
    if height >= 1:
        print( "    "*(3-height), "moveTower:", height, fromPole, toPole )
        moveTower(height-1,fromPole,withPole,toPole)
        moveDisk(fromPole,toPole,height)
        moveTower(height-1,withPole,toPole,fromPole)
    #print(withPole)

def moveDisk(fp,tp,height):
    print("    "*(4-height), "moving disk", "~"*(height), "from",fp,"to",tp)


moveTower(3,"A","B","C")

The output is:

输出是：

moveTower: 3 A B
     moveTower: 2 A C
         moveTower: 1 A B
             moving disk ~ from A to B
         moving disk ~~ from A to C
         moveTower: 1 B C
             moving disk ~ from B to C
     moving disk ~~~ from A to B
     moveTower: 2 C B
         moveTower: 1 C A
             moving disk ~ from C to A
         moving disk ~~ from C to B
         moveTower: 1 A B
             moving disk ~ from A to B

回答by dilbert

You should print the call of each moveTower to see the changes in its arguments. Recursion typically propagates changes through arguments. A sequence number is helpful for showing order (of course, the printing to the console is ordered too).

您应该打印每个 moveTower 的调用以查看其参数的变化。递归通常通过参数传播更改。序列号有助于显示顺序（当然，打印到控制台也是有顺序的）。

def seq_nummer():
    num = 0
    while True:
        num += 1
        yield num

seq_num = seq_nummer()

def moveTower(height, fromPole, toPole, withPole):
    print("seq: %d" % seq_num.next())
    print("height: %d, fromPole: %s, toPole: %s, withPole: %s" % (height, fromPole, toPole, withPole))
    if height >= 1:
        moveTower(height-1, fromPole, withPole, toPole)
        moveDisk(fromPole, toPole)
        moveTower(height-1, withPole, toPole, fromPole)

def moveDisk(fp,tp):
    print("moving disk from",fp,"to",tp)

moveTower(3,"A","B","C")

回答by Abhishek Bansal

moveTower(height-1,fromPole,withPole,toPole)

Move all discs but one from the initial pole to the in-between pole, using the third pole.

使用第三个极点将所有圆盘从初始极点移动到中间极点。

moveDisk(fromPole,toPole)

Move the last disc from initial Pole to final Pole. Now last disc is at its correct position and does not need to be moved.

将最后一个圆盘从初始极点移动到最终极点。现在最后一个圆盘处于正确位置，不需要移动。

moveTower(height-1,withPole,toPole,fromPole)

Move all discs from in-between Pole to final pole, using the first pole if required.

将所有圆盘从中间极移动到最后极，如果需要，使用第一个极。