Towers of Hanoi recursive calls
<pre><code>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')
</code></pre>

<p>Please can someone explain why this code completes the recursive call on line 12 with <code>n</code> decrementing to 1, then does another call to <code>n = 2</code> 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.</p>

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

<pre><code>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)
</code></pre>

<p>And here goes the explanation. Look at the picture -></p>

<p><a href="http://i.stack.imgur.com/krc1J.png"><img src="http://i.stack.imgur.com/krc1J.png" alt="enter image description here"></a></p>

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

<pre><code>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
</code></pre>

<p>Hope it helps :)</p>

<p>You can also find some good explanations here : <a href="http://stackoverflow.com/questions/1223305/tower-of-hanoi-recursive-algorithm">Tower of Hanoi: Recursive Algorithm</a></p>

<p>For Animation : <a href="https://www.cs.cmu.edu/~cburch/survey/recurse/hanoiex.html">https://www.cs.cmu.edu/~cburch/survey/recurse/hanoiex.html</a></p>

python algorithm recursion towers-of-hanoi