A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

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 the line:

return number * factorial(number - 1)

which 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 tricky ...