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