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) gets called. In order to track that the computer is still in the middle of factorial(3), the computer pushes that info onto a call stack:

The computer then proceeds to execute factorial(2). Now, factorial(2), in turn, calls factorial(1). Before the computer dives into factorial(1), though, the computer needs to remember that it’s still in the middle of factorial(2), so it pushes that onto the call stack as well:

The computer then executes factorial(1). Since 1 is the base case, factorial(1) completes without the factorial method again.

Even after the computer completes factorial(1), it knows that it’s not finished with everything it needs to do since there’s data in the call stack, which indicates that it is still in the middle of running other methods that it needs to complete. As you will recall, stacks are restricted in that we can only inspect the top (in other words, the final) element. So the next thing the computer does is peek at the top element of the call stack, which currently is factorial(2).

Since factorial(2) is the last item in the call stack, that means that factorial(2) is the most recently called method and therefore the immediate method that needs to be completed.

The computer then pops factorial(2) from the call stack

and completes running factorial(2).

Then the computer looks at the call stack to see which method it needs to complete next, and since the call stack is currently

it pops factorial(3) from the stack and completes it.

At this point, the stack is empty, so the computer knows it’s done executing all of the methods, and the recursion is complete.

Looking back at this example from a bird’s-eye view, you’ll see that the order in which the computer calculates the factorial of 3 is as follows:

1. factorial(3) is called first.
2. factorial(2) is called second.
3. factorial(1) is called third.
4. factorial(1) is completed first.
5. factorial(2) is completed based on the result of factorial(1).
6. Finally, factorial(3) is completed based on the result of factorial(2).

Interestingly, in the case of infinite recursion (such as the very first example in our chapter), the program keeps on pushing the same method over and over again onto the call stack, until there’s no more room in the computer’s memory—and this causes an error known as stack overflow.