Towers of Hanoi Python - understanding recursion [duplicate]

Question

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:

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

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 fp and tp can change from A to B to C. Sorry if this is bit of a broad question! Any help would be greatly appreciated!

Atrip

Maybe this answer ist helpful: https://mcmap.net/q/279598/-tower-of-hanoi-recursive-algorithm – Omnipotent

I would suggest sticking print(height, fromPole, toPole, withPole) at the top and seeing what happens! – Crumpet

Thank you so much to everyone who has answered! Feel a lot more confident of my understanding now :) – Atrip

Answer 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

Tondatone

Thank you so much :) in your explanation of the output, you have omitted an argument from the moveTower function, (e.g moveTower: 3 A B, when in my example moveTower(height, fromPole,toPole,withPole)) is this simply because the third argument isn't really utilised? could i get rid of it? – Atrip

This third argument is redundant but convenient, so I suggest to leave it in the code. The output is supposed to visualize the nesting of the various recursive operations. – Tondatone

also, where you have in your output, moving disk i'm assuming this relates to my moveDisk? thanks again! – Atrip

sorry i know this was a while ago, I'm still stuck! i came back to this today and i realised that i don't understand how in this part of the code: moveTower: 3 A B moveTower: 2 A C moveTower: 1 A B (the top 3 lines) why is the 3rd line, 1 AB wouldn't it be 1 AC? @Tondatone – Atrip

Answer 2

here is what it does. The starting position is:

A|321
B|
C|

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

A|3
B| 
C|21

then, moveDisk(fromA, toB) does

A|
B|3
C|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).

Cellulose

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

Quickfreeze

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

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

Minatory

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

Puentes