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

piet.t
  • 11,718
  • 21
  • 43
  • 52
neoraiden
  • 55
  • 1
  • 6

2 Answers2

4

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

enter image description here

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

Community
  • 1
  • 1
jbsu32
  • 1,036
  • 1
  • 11
  • 31
  • Thanks for the explanation, the code I used was from the edx MIT introduction to computation and programming using python. I tried to recreate it without copying it verbatim and realised I couldn't get the correct order and didn't understand each step. – neoraiden Aug 31 '16 at 03:08
1

First, an aside: the code you show contains an error on line 9, which is not indented legally.

Execution begins with line 19, which calls towers(3,...), which proceeds up to line 12, where it calls towers(2,...), which proceeds up to line 12, where it calls towers(1,...), which prints something and returns. When it returns, execution resumes in the towers(2,...) invocation, and resumes at line 16, as you observed.

P. Pearson
  • 116
  • 2