This will be a tutorial on simulating recursion with a stack. I developed this tutorial after using this technique to solve 472B - Уроки дизайна задач: учимся у жизни.

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

That is, the first thing that we put on our stack is a call to factorial(3). While there is still something on the stack, we pop it off and proceed along with it.

The idea is that there are two different actions that we can perform after popping off the stack. The instructions are encoded in that pop. We can either be at the beginning of a brand new call OR we can be picking up from a previous call. If we are performing a brand new function call then we unpack the data which in included (just the value of n) and execute the body like normal (i.e. checking for the base condition).

The only funny part is that since it is just a single function and we can't use return directly, we have to simulate "returning". I have chosen to do that by including a global variable. This works because the return value of a function is ever checked by a single point (i.e. the caller). This is a property of how functions are called in python.

The more interesting case is when we hit a recursive call. What we have to do is two things — save the state of the function on that stack (i.e. so we can pick it up later) and then instructions to make a brand new function call. In each case the data that we save on the stack is the same (i.e. it's just the local variables). In both cases it's the same local variable (i.e. n), but if it was a more complicated function then we would save additional local variables on the stack.

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

Here is the final picture.