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, an aside: the code you show contains an error on line 9, which is not indented legally.</p>

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

python algorithm recursion towers-of-hanoi