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 implementation should be familiar to anyone with experience with recursion, as it is often used as a basic example.

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