Removing a recursion in Python, part 1

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

This seems like a very verbose, kinda-sorta continuation passing approach. Except that he's building the eventual continuation as a list of primitive functions instead of a complex function.

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
         store_i_minus_1, store_i_minus_2 = result, store_i_minus_1
      return result

You will note that the the new example has no allocation to the heap and is the full efficient iterative version.

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.

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.

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.

Am I the only one who read this and thought: hmm, for any number 32 or higher, the minimum cost would always be 5? Who cares about recursion when it's such a constrained problem? :)

I don't really get the point of this. As far as I can tell, the code is doing the same thing as before but has become (at least to me) much harder to understand.

I'm pretty sure that the words "tail recursion" or "tail call" should appear somewhere in this article - see e.g. https://en.wikipedia.org/wiki/Tail_call which also explains in a remarkably simple way how tail recursion relates to iterative constructs (as are found, e.g. in Python). Why do people write 'introductory' articles that don't even mention common terminology?