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 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 "call 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. But in order to compute factorial(2), we need to compute factorial(1) and then multiply the result by 2. To compute factorial(1)... well that's the base case. factorial(1) = 1. Now that we've reached the base case, we have enough information to evaluate factorial(2). Now that we know factorial(2), we can compute factorial(3). And we have the final answer.

For reasons that will soon become clear, notice we can equivalently write this function as follows:

def factorial(n):
    if n == 1:
        return 1
    else:
        k = factorial(n-1)
        fact = n * k
        return fact

Notice by writing factorial() in this way, we can identify different canonical "parts" of the function:

def factorial(n):
    if n == 1:             # BASE CASE
        return 1           # BASE CASE
    else:                  # RECURSIVE CASE:
        k = factorial(n-1) # RECURSIVE CASE: RECURSIVE CALL
        fact = n * k       # RECURSIVE CASE: RESUME FROM RECURSIVE CALL
        return fact        # RECURSIVE CASE: RETURN

Notice how we can split up this definition into different regions. We can map these regions to the following iterative definition: