Towers Of Hanoi Python - Understanding Recursion

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: d

Solution 1:

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

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

Solution 2:

here is what it does. The starting position is:

A|321B|
C|

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

A|3B| 
C|21

then, moveDisk(fromA, toB) does

A|
B|3C|21

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

A|
B|
C|321

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

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

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

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

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

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

Solution 3:

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.

The question can be seen as a duplicate of this question.

Solution 4:

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).

defseq_nummer():
    num = 0whileTrue:
        num += 1yield num

seq_num = seq_nummer()

defmoveTower(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)

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

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

Solution 5:

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.