Tutorial: Simulating recursion with a stack

Revision en11, by ebanner, 2018-04-21 07:11:59

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!


  Rev. Lang. By When Δ Comment
en11 English ebanner 2018-04-21 07:11:59 105 (published)
en10 English ebanner 2018-04-21 07:07:07 652
en9 English ebanner 2018-04-21 07:02:18 1255
en8 English ebanner 2018-04-21 06:34:15 10
en7 English ebanner 2018-04-21 06:30:39 2049
en6 English ebanner 2016-12-10 22:52:18 135
en5 English ebanner 2016-12-10 22:50:48 1037 Tiny change: '3q8/pub?w=589&h=173)\n\nHere,' -
en4 English ebanner 2016-12-10 21:54:29 452 Tiny change: 'result by 3. Since we' -
en3 English ebanner 2016-12-10 21:42:57 1168 Tiny change: 'd84/pub?w=475&h=142)' -
en2 English ebanner 2016-12-10 21:04:46 760 Tiny change: ' = n * k\n\n ' -
en1 English ebanner 2016-12-10 20:46:16 967 Initial revision (saved to drafts)