This will be a tutorial on simulating recursion with a stack. This approach assumes a linear chain of recursion calls found in functions like factorial()
, as opposed to "branching" recursion which results in functions such as naive O(a^n)
implementations of fibonnaci()
, though I believe this approach can be extended to such cases. 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 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
k = factorial(n-1)
fact = n * k
return fact