A Common-Sense Guide to Data Structures and Algorithms in Python, Volume 1

Recursion in the Eyes of the Computer

To complete your understanding of recursion, we need to see how the computer itself processes a recursive function. It’s one thing for humans to reason about recursion using the earlier “napkin” method. However, the computer has to do the tricky work of calling a function from within the function itself. So let’s break down the process of how the computer executes a recursive function.

Say that we call factorial(3). Since 3 isn’t the base case, the computer reaches this line:

return number * factorial(number - 1)

This then launches the function factorial(2).

But there’s a catch. When the computer begins to run factorial(2), did the computer yet complete running factorial(3)?

This is what makes recursion ...