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). We repeat this process until the values of factorial(2) is computed.

To more closely mirror the stack simulation, we can rewrite our definition of factorial() as follows:

Here, factorial() consists of distinct regions of code corresponding to the base case, recursive call, and instructions after the recursive call.

We can make the following transformation to convert our recursive factorial() implementation to an iterative one: