Removing a recursion in Python, part 1
The article doesn&#x27;t explain the problem of converting recursion to iteration fully. There is a lot more detail.<p>Most recursion can be implemented using a loop and a stack. If the recursive expression is self contained in the return call, then you don&#x27;t need a stack.<p>For example:<p><pre><code>  def somefunc(x):
      if x &lt;= 0:
          return 0
      return somefunc(x-1)
</code></pre>
is equal to:<p><pre><code>  def somefunc(x)
      while x &gt; 0:
         x = x - 1
      return x
</code></pre>
But if the recursion isn&#x27;t self contained:<p><pre><code>  def somefunc(x):
      if x == 0:
          return 0
      return somefunc(x-1) + 1
</code></pre>
then the iterative version 
looks like this:<p><pre><code>  def somefunc(x)
      stack = []
      while x &gt; 0:
         stack.append(x)
         x = x - 1
      while len(stack) != 0:
         x = x + stack[-1]
         stack = stack[:-1]
    return x
   
</code></pre>
During Recursion your program will use an internal stack to keep track of previous context. This is called the call stack. Whether or not you use iteration or recursion for the last example you will need a stack.<p>The last example is actually less efficient than the recursive version because you are moving the call stack to the heap. The heap is slower than the call stack but the heap essentially has no limits so you won&#x27;t encounter stack overflow.<p>In the first example of recursion you will actually benefit from conversion to iteration because you get rid of the stack all together in the iterative example. Some languages will be able to recognize this type of recursion and do an optimization step called &quot;tail-recursion optimization&quot; in which the compiler actually gets rid of the need for a the call stack. Python does not do this, however.<p>The story doesn&#x27;t end here, however. There are examples of recursion where you cannot create a straightforward iterative version.<p>For example:<p><pre><code>  def somefunc(x):
      if x &lt;= 0:
          return 0
      return somefunc(x-1) + somefunc(x-2)
</code></pre>
The straight forward conversion using an explicit stack looks like this:<p><pre><code>  def somefunc(x)
      stack = []
      while x &gt; 0:
         stack.append(lambda: somefunc(x-2))
         x = x - 1
      while len(stack) != 0:
         x + stack[:-1]()
         stack = stack[:-1]
      return x
</code></pre>
You will note that the straightforward conversion doesn&#x27;t get rid of recursion. The reason is because the previous context is basically another recursive call.<p>You will note that the recursive version of this function actually does the same multiple recursive calls twice which leads to unnecessary repeated calculations. It is possible to optimize this repetition using something called memoization. However memoization requires and does not get rid of recursion.<p>It is not possible to imitate this &quot;inn-efficiency&quot; in an iterative form. The only way to do it is to do an optimization step similar to memoization before iterating. This step, however radically changes the way you think about the problem. It literally reverses the recursion from a top down approach to a bottom up approach. Here is what the iterative form looks like:<p><pre><code>  def somefunc(x):
      store = [None for _ in range(x)]
      store[0] = 0
      for i in range(1, len(store)):
         store[i] = store[i-1] + store[i-2] if i-2 &gt;= 0 else 0
      return store[-1]
</code></pre>
This method is called &quot;Dynamic programming using the tabular method.&quot;<p>You will note that this version of the function still allocates storage to the heap with &quot;store&quot;<p>There is still a further optimization step you can do here as well. This optimization is basically noticing that you don&#x27;t need to memorize the entire store in the algorithm. You only need the previous two values.<p><pre><code>  def somefunc(x):
      store_i_minus_1 = 0
      store_i_minus_2 = 0
      for i in range(1, len(store)):
         result = store_i_minus_1 + store_i_minus_2
         store_i_minus_1, store_i_minus_2 = result, store_i_minus_1
      return result
</code></pre>
You will note that the the new example has no allocation to the heap and is the full efficient iterative version.<p>Although my final example was applied to a recursive function that called itself twice in a single expression. The final technique I showed you can be applied to all forms of recursion to yield an iterative version WITHOUT the need to create an explicit stack in the heap. It is the ultimate optimization step in a procedural language.<p>One thing to note is that the final optimization can only be done in a procedural language. For a Functional programming language you will need to utilize another method.