Towers of Hanoi recursion in python, understanding the change in disc destination

Question

I am trying to improve my understanding of the code for the recursive solution to the towers of hanoi in python.

this code:

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

will print the correct moves required to solve the puzzle and so i asked on stack overflow a while ago for an explanation on how it does so. I was given this answer

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

The only thing I do not understand about this explanation is how within the recursion the disc destination (peg a,b,c) changes? the 3rd line - moveTower: 1 A B, is correct and I know that the disc should be moved from A to B but I don't understand how we went from A to C (the 2nd line) to the new destination being B! This is hard to explain, if you don't understand what I mean please ask but I would really like some help in understanding this!

this is what i understand the code would look like for 3 discs from=A, to=B, with=C and I have written what i think the recursion would look like (this is ignoring most of the code, I'm just focusing on the top part

def moveTower(3,A, B, C):
    if height >= 1:

        moveTower(2,A,C,B)
            moveTower(1,A, C, B) #so this line of code should be A,B,C but why? as in recursion do we not simply repeat the code again and again? so why would it change if the code initially is ACB why does it change to ABC? 
            moveDisk(A,B,3)
            moveTower(1,C,B,A)

hi @Jasper surely in the recursion the arrangement of fromePole toPole withPole: moveTower(height-1,fromPole,withPole,toPole) stays the same? and therefore I don't understand how it changes? — heather, Apr 25 '14 at 10:46
It does **not** stay the same! The function parameters are `from, to, with`, the first recursive call is `from, with, to` and the second is `with to from`. — Jasper, Apr 25 '14 at 10:51
@jasper sorry I'm a beginner, could you explain why this occurs? — heather, Apr 25 '14 at 10:58
http://en.wikipedia.org/wiki/Tower_of_Hanoi#Recursive_solution please do at least **some** research yourself... — Jasper, Apr 25 '14 at 11:03
@Jasper i have. if you don't want to help thats fine. no need to be like that. — heather, Apr 25 '14 at 11:14
Is your question really "how" or "why" the pegs are changed (and in which order)? — Jasper, Apr 25 '14 at 11:39
@Jasper how. so i would visualise the recursion like this: (just the first part) def moveTower(height,fromPole, toPole, withPole): if height >= 1: moveTower(height-1,fromPole,withPole,toPole) moveTower(height-1,fromPole,withPole,toPole) moveDisk(fromPole,toPole,height) moveTower(height-1,withPole,toPole,fromPole) and so to me..the pegs wouldn't change in the recursion? but obviously I'm going wrong in some way! — heather, Apr 25 '14 at 11:42
sorry thats not very clear, its hard to write code in the comments! — heather, Apr 25 '14 at 11:43
Do you understand that the order in which parameters are passed to a method matter? `divide(x, y)` is not the same as `divide(y, x)`. While you are passing the same parameters to the function, you are passing them in a different order, i.e. the parameters have different "roles", to call it that way. What was the `from_pole` in one call, is the `with_pole` in another. — tobias_k, Apr 25 '14 at 11:46
yes i understand that @tobias_k what i don't understand is how the order changes on the 3rd line of this code. how does it go from being from, with, to --> with, to, from — heather, Apr 25 '14 at 11:54
I do absolutely not understand what you are asking. Do you mean why the parameters change? Because the function is called with different parameters! Or do you ask why the function is called with different parameters? Because that's how the algorithm works! Maybe this helps: `moveTower(height-1, fromPole, withPole, toPole)` is equivalent to the more verbose `moveTower(height=height-1, fromPole=fromPole, toPole=withPole, withPole=toPole)` — tobias_k, Apr 25 '14 at 12:00
@tobias_k sorry my question is worded badly, i will edit it and hopefully explain my situation better! — heather, Apr 25 '14 at 12:02

score 1 · Accepted Answer · answered Apr 25 '14 at 12:31

Don't mix up code that is written in the program and the code that is executed, especially with regard to variable names!

def moveTower(3, A, B, C):
    if height >= 1:

        moveTower(2,A,C,B)
            moveTower(1,A, C, B) #so this line of code should be A,B,C but why? as in recursion do we not simply repeat the code again and again? so why would it change if the code initially is ACB why does it change to ABC? 
            moveDisk(A,B,3)
            moveTower(1,C,B,A)

consider this snippet from the correct code with shorter variable names:

def moveTower(height, a, b, c):
    if height >= 1:
        moveTower(height-1, a, c, b)

If the first call is moveTower(3, 'Peg1', 'Peg2, 'Peg3'), this means that 3 disks (the whole tower) must be moved from peg 1 to peg 2 while using peg 3 as temporary storage. Now within the function moveTower, the variable a gets 'Peg1', b gets 'Peg2' and c gets 'Peg3'.

Now the recursion starts: to move 3 disks from peg 1 to peg 2, you start by moving two disks to the "helper peg", and you use the third peg as new helper:

moveTower(2, a, c, b) # in the first call, a=Peg1, b=Peg2, c=Peg3

This results in another invocation of moveTower, but this time, we have: a gets 'Peg1', b gets 'Peg3' and c gets 'Peg2', because c and b are swapped in the call. Then another step of recursion occurs:

moveTower(1, a, c, b)

The variable names are the same, but now they have different values: c is 'Peg2'! So in the next instance of moveTower, we have (same as the first invocation): a gets 'Peg1', b gets 'Peg2' because it is the second parameter, and in the call to moveTower, the second parameter is c='Peg2' and the new c gets 'Peg3' from the former b.

I hope this helps. You might also understand it better if you do the recursion by hand (using pen and paper) and writing down, which variable has which content in every step.

Towers of Hanoi recursion in python, understanding the change in disc destination

1 Answers1