Towers of Hanoi Python - understanding recursion

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!

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