This will be a tutorial on simulating recursion with a stack. I developed this tutorial after using this technique to solve 472B - Уроки дизайна задач: учимся у жизни.
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 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)
. Once
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: