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: