A Common-Sense Guide to Data Structures and Algorithms

Recursion in the Eyes of the Computer

If you think about our factorial method, you’ll realize when we call factorial(3), the following happens:

The computer calls factorial(3), and before the method is complete, it calls factorial(2), and before factorial(2) is complete, it calls factorial(1). Technically, while the computer runs factorial(1), it’s still in the middle of factorial(2), which in turn is running within factorial(3).

The computer uses a stack to keep track of which functions it’s in the middle of calling. This stack is known, appropriately enough, as the call stack.

Let’s watch the call stack in action using the factorial example.

The computer begins by calling factorial(3). Before the method completes executing, however, factorial(2) ...