title: Python Recursion Overhead
body: <p>I have written a python program that solves Sudoku and want to make it faster. The core operation is a depth first search function which I implement as recursion. I thought I could eliminate the recursion overhead by re-writing the depth first search procedure as a loop which manages a data stack (simply a list); but it turns out that performance is not significantly different. I am pretty sure that the loop version is procedurally equivalent to the recursive version.
  Is it because the data stack I use is not fast in pushing/popping? Or python interpreter really makes very good use of hardware? Can someone help me figure out what can be done? 
  Profiling is attached. </p>
  
  <p>search_naked is the recursive function.</p>
  
  <pre><code>                      2446265 function calls (1813295 primitive calls) in 4.576 seconds
  
     Ordered by: internal time, cumulative time
     List reduced from 31 to 20 due to restriction &lt;20&gt;
  
     ncalls  tottime  percall  cumtime  percall filename:lineno(function)
  709255/79779    2.136    0.000    2.136    0.000 sdkx.py:251(search_naked)
       3514    1.539    0.000    3.994    0.001 sdkx.py:106(propagate)
    3514/20    0.239    0.000    4.389    0.219 sdkx.py:234(dfs)
         20    0.135    0.007    4.528    0.226 sdkx.py:468(solvestring)
       3901    0.098    0.000    0.113    0.000 sdkx.py:82(Assume)
     467283    0.071    0.000    0.071    0.000 {method 'add' of 'set' objects}
       3514    0.050    0.000    0.050    0.000 {method 'copy' of 'dict' objects}
     378200    0.048    0.000    0.048    0.000 {method 'discard' of 'set' objects}
          1    0.047    0.047    4.576    4.576 sdkx.py:487(solvefile)
  </code></pre>
  
  <p>And here is the loop counterpart - search_naked3</p>
  
  <pre><code>         2825303 function calls (2821809 primitive calls) in 4.367 seconds
  
     Ordered by: internal time, cumulative time
     List reduced from 32 to 20 due to restriction &lt;20&gt;
  
     ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     144657    1.967    0.000    2.154    0.000 sdkx.py:148(search_naked3)
       3514    1.285    0.000    3.760    0.001 sdkx.py:106(propagate)
    3514/20    0.240    0.000    4.156    0.208 sdkx.py:221(dfs)
     443513    0.114    0.000    0.114    0.000 {method 'pop' of 'list' objects}
         20    0.109    0.005    4.269    0.213 sdkx.py:455(solvestring)
          1    0.097    0.097    4.367    4.367 sdkx.py:474(solvefile)
       3901    0.096    0.000    0.112    0.000 sdkx.py:82(Assume)
     467283    0.072    0.000    0.072    0.000 {method 'add' of 'set' objects}
  </code></pre>
  
  <p>[Edit]
  Here attached the two functions.</p>
  
  <pre><code>def search_naked(Ls, LsL, Tmask, D, NLID,N, locs, masks):  #Find the smallest naked subgroup.
      #global naked, naked_mask, M_size
      LsL1, K  = LsL+1, LsL+N
      for nextLID in xrange(NLID, N):
          Tmask1 =  Tmask|masks[nextLID]
          D1=d_counter[Tmask1]
          if LsL1==D1:
              if D1 &lt;N:
                  return Ls+locs[nextLID], Tmask1, D1
              return 0,0,0
          if LsL1&gt;D1:
              return False
          if D1+nextLID &gt; K:# or D1&gt;=M_size: 
              continue
          result = search_naked(Ls+locs[nextLID], LsL1, Tmask1, D1, nextLID+1,N, locs, masks)
          if result!=(0,0,0):
              return result
  
  
      return 0,0,0
  
  
  
  def search_naked3(locs, masks, N):  #Find a subgroup in a deep first manner without recussion. counter is the stack for DFS purpose.
  
      counter, i, Len, bm,K = [],0, 1,0,N-1
      #i: the current index of a cell to be augmentally considered and checked with for subgroup.
      #bm: base mask is the ORed value of previously selected masks, this is used with the current cell to generate a new mask for checking purpose
      #counter: the stack structure storing (i,bm) pairs, which are used when returning from DFS
      #Len: this is a derived value, as len(counter)+1, Len is maintained to avoid calling len() function.
      #At each stage, there are len(counter)+1 cells are being combined consdered/checked as a subgroup, including len(counter) previous cells and
      #the current cell indicated by i;
      #K=N-1 does not change over the while loop; so save same redundant computation.
      while True:
          TM = bm|masks[i]       #TM (total mask): the mask to check
          D=d_counter[TM]         #D the number of ones in TM.
  
          if D == Len:        #That is if a subgroup is formed if D==Len&lt;N; or we are checking the entire group (D==Len==N)
  
              return (0,0,0) if D==N else (locs[i]+sum([locs[c] for (c,m) in counter]), TM, D)   #return a subgroup, else, return the flag that no subgroup is found
          #From now on, D is assumed &gt; Len. Situation of D&lt;Len is impossible due to the treatment before the loop.
          if  D ==N or D - Len &gt; K-i: #Current combination of cells is "blown": either N digits have be provided by less than N locations; or 
                                      #there is not enought number (K-i) of unconsidered cells that could possiblly accommodate D-Len digits.
                                      #If blown, we need to check the next cell, unless cell i is already the last of the N cells.
              if i&lt;N-1:               #If there is a next cell, simple increase i, and continue with while loop. Len, bm should not change,
                  i+=1
                  continue
              else:                   #Now threat the sitation where i is already pointing at the last of N cells.
                  if Len-1:           #If there is still something in the stack (indicated by Len-1), 
                      i,bm =counter.pop()    #pop from the stack to go back to one level higher, using the older base mask
                      i+=1                    #and try the next cell at that higher level.
                      Len-=1                  #Of course, the we are considering 1 less cells. 
                      continue                #continue with the while loop
                  break               #If there is nothing left in the stack -&gt; all combinations have been checked. The only exit of the while loop.
          #From now on: Len cells contributed D digits, Len&lt;D and not blown. Prepare to go one level deeper, unless the current cell is already the last of N cells.
          if i&lt; N-1:      #this is the situation in which, the current cell indicated by i is not the last of N cells,
              counter.append((i,bm))  # push to stack
              bm=TM                   #base mask is updated as the current total mask
              i+=1                    #The firt cell to consider in the deeper level is the one just next to the current cell of this level.
              Len+=1                  #of course, we are considering a more cell.
              continue                #continue with the while loop.
          #Now, we treat the situation in which the current combination of cells already include the last of N cells, ie, i==N-1.
          #We cannot go deeper, therefore we return to a higher level.
          i,bm =counter.pop()         # Pop the stack, returning to the higher level, recovering base mask 
          i+=1                        # and the next cell to consider in the higher level. 
          Len-=1                      #Of course, we are considering 1 less cells in the combination.
      return 0,0,0                    #The loop must be bronken! That means all combinations have been considered without finding a subgroup. Return the flag
  </code></pre>