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:
