Removing a recursion in Python, part 1 (ericlippert.com)

Is this programing 101?

Thanks, this is very interesting. I am enrolled in a CS Bsc. (night courses) and while we learned about the different techniques of recursive programming, we never learned how to convert a recursive solution into an iterative one.

A more stable link would be https://ericlippert.com/2018/12/03/removing-a-recursion-in-p...

The article doesn't explain the problem of converting recursion to iteration fully. There is a lot more detail.

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't need a stack.

For example:

  def somefunc(x):
      if x <= 0:
          return 0
      return somefunc(x-1)

is equal to:

  def somefunc(x)
      while x > 0:
         x = x - 1
      return x

But if the recursion isn't self contained:

  def somefunc(x):
      if x == 0:
          return 0
      return somefunc(x-1) + 1

then the iterative version looks like this:

  def somefunc(x)
      stack = []
      while x > 0:
         stack.append(x)
         x = x - 1
      while len(stack) != 0:
         x = x + stack[-1]
         stack = stack[:-1]
    return x
   

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.

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't encounter stack overflow.

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 "tail-recursion optimization" in which the compiler actually gets rid of the need for a the call stack. Python does not do this, however.

The story doesn't end here, however. There are examples of recursion where you cannot create a straightforward iterative version.

For example:

  def somefunc(x):
      if x <= 0:
          return 0
      return somefunc(x-1) + somefunc(x-2)

The straight forward conversion using an explicit stack looks like this:

  def somefunc(x)
      stack = []
      while x > 0:
         stack.append(lambda: somefunc(x-2))
         x = x - 1
      while len(stack) != 0:
         x + stack[:-1]()
         stack = stack[:-1]
      return x

You will note that the straightforward conversion doesn't get rid of recursion. The reason is because the previous context is basically another recursive call.

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.

It is not possible to imitate this "inn-efficiency" 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:

  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 >= 0 else 0
      return store[-1]

This method is called "Dynamic programming using the tabular method."

You will note that this version of the function still allocates storage to the heap with "store"

There is still a further optimization step you can do here as well. This optimization is basically noticing that you don't need to memorize the entire store in the algorithm. You only need the previous two values.

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

  def cost(s):
    if s <= 1:
      return 0
    if s % 2 == 0:
      return 1 + cost(s // 2) 
    return min(1 + cost(s - 1), 5)

  def cost(s):
      if s <= 1:
         return 0
      store = [None for _ in range(s+1)]
      store[0] = 0
      store[1] = 0
      for i in range(2, s+1):
         store[i] = 1 + store[i//2] if i%2 == 0 else min(1 + store[i-1], 5)
      return store[-1]