Fun fact: from beginning to end this blog post took me 16 months!

This will be a tutorial on simulating recursion with a stack. I developed this tutorial after using this technique to solve 472B - Design Tutorial: Learn from Life.

Consider the following recursive definition of the factorial() function.

def factorial(n):
   return n*factorial(n-1) if n>1 else 1

This definition is compact, concise, and mirrors the definition that appears in math textbooks very closely. In many ways it is the most natural way to define factorial().

However, there is a problem. For very large values of n, you will see that we will get a StackOverflowError.

To understand why this is the case, you must understand that recursion is implemented in Python (and most other languages) as growing and shrinking a stack in memory.

For example, consider the following simulation of the computation of factorial(3).

That is, to compute factorial(3), we need to compute factorial(2) and then multiply the result by 3. Since we have very specific instructions to perform after computing factorial(2) (i.e. multiplying by 3), we need to save these instructions so we can come back to them after computing factorial(2). This is accomplished by saving our local state (e.g. local variables) on a stack and then shifting our focus to factorial(2). We repeat this process until the values of factorial(2) is computed.

To more closely mirror the stack simulation, we can rewrite our definition of factorial() as follows.

Here, it is more clear as to the order of operations. We have distinct regions of code corresponding to first checking for the base case, then making the recursive call if that condition is not met, and instructions after the recursive call (as well as instructions for computing the base case).

If we wish to convert our recursive definition to an iterative one we can do so with the following transformation.

And here is what it looks like.

Note that the RESULT above the table refers to a global variable "outside" of the stack.

How this proceeds is that while there is something on the stack we pop it off and perform the action that's associated with it. The first entry on the stack should be intuitive. Our goal is to compute factorial(3) so we put a call to factorial(3) on the stack.

In the CALL case, we unpack the associated data in that entry (i.e. the function arguments) and execute the body of the function. If we hit the base case we "return" by setting a global variable which can be checked by the "caller". If we hit the recursive case we do something fancier.

In the recursive case we put entries on the stack to simulate recursion. That is, the next time we pop an entry from the stack, we should find a function call. If that is the base case, then the next time we pop from the stack we should get the value from that function call and resume execution. That is exactly what is going on here.

What if we had multiple recursive calls in our function? The only change we would have to make multiple return actions (i.e. RESUME1, RESUME2, ...) for the number of recursive calls in our function.

What about code before checking for the base or recursive case? That code would go right above the case check (in the body of the action == CALL conditional).

I hope you enjoyed it!