Towers of Hanoi recursive calls

Question

1
2   def printMove (to, fr):
3       '''Prints the moves to be executed'''
4       print 'move from ' + str (fr) + ' to ' + str (to)
5   
6   def towers (n, fr, to, sp):
7       if n == 1:            
8     
9       printMove (to, fr)    # 
10      
11      else:
12          towers (n-1, fr, sp, to)  
13                    
14                   
15                 
16          towers (1, fr, to, sp)
17          towers (n - 1, sp, to, fr)
18  
19  towers (3, 'fr', 'to', 'sp')

Please can someone explain why this code completes the recursive call on line 12 with n decrementing to 1, then does another call to n = 2 again and then move to line 16 after? I have been using python tutor and am trying to understand each step and why the algorithm works.

Answer 1

First of all, your code is not perfectly alright. Here is the changed towers function for you ->

def towers (n, fr, to, sp):
    if n == 1:            
        printMove (to, fr)
    else:
        towers (n-1, fr, sp, to)
        printMove (to,fr)
        towers (n-1, sp, to, fr)

And here goes the explanation. Look at the picture ->

By calling Movetower(3,a,b,c), you intend to move all the 3 discs from tower A to tower B. So the sequential calls are ->

1. Movetower(3,a,b,c)  // No Move needed
2. Movetower(2,a,c,b)  // No move needed
3. Movetower(1,a,b,c)  // Here is the time to move, move disc1 from a to b
4. Movetower(2,a,c,b)  // Returning to this call again, this is the time to move disc2 from a to c
5. Movetower(1,b,c,a)  // Again the time to move, this time disc1 from b to c
6. Movetower(3,a,b,c)  // Returning to this call again, this is the time to move disc3 from a to b
7. Movetower(2,c,b,a)  // Not the time to move
8. Movetower(1,c,a,b)  // Here is the time to move, move disc1 from c to a
9. Movetower(2,c,b,a)  // Returning to this call again, this is the time to move disc2 from c to b
10.Movetower(1,c,a,b)  // Here is the time to move, move disc1 from a to b

Hope it helps :)

You can also find some good explanations here : Tower of Hanoi: Recursive Algorithm

For Animation : https://www.cs.cmu.edu/~cburch/survey/recurse/hanoiex.html