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