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:

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 tricky for the computer. Until the computer reaches the end keyword of factorial(3), it’s not done with factorial(3). So we enter into a weird situation. The computer didn’t yet complete executing factorial(3), yet it’s starting to run factorial(2) while still in the middle of factorial(3).

And factorial(2) isn’t the end of the story, because factorial(2) triggers factorial(1). So it’s a crazy thing: while still in the middle of running factorial(3), the computer calls factorial(2). And while running factorial(2), the computer runs factorial(1). It turns out, then, that factorial(1) runs in the middle of both factorial(2) and factorial(3).

How does the computer keep track of all of this? It needs some way to remember that after it finishes factorial(1), it needs to go back and finish running factorial(2). And then it needs to remember to complete factorial(3) once it completes factorial(2).

The Call Stack

Luckily, you recently learned about stacks in Chapter 9, . 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.

Here’s how the call stack works in the context of our factorial example.

The computer begins by calling factorial(3). Before the method completes executing, however, factorial(2) gets called. To track that the computer is still in the middle of factorial(3), the computer pushes that information onto a call stack:

This indicates that the computer is in the middle of factorial(3). (Really, the computer also needs to save which line it’s in the middle of, and some other things like variable values, but I’m keeping the diagrams simple.)

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 calling the factorial method again.

After the computer completes factorial(1), it checks the call stack to see whether it’s in the middle of any other functions. If there’s something in the call stack, it means that the computer still has work to do—namely, wrap up some other functions it was in the middle of.

If you recall, stacks are restricted in that we can only pop its top element. This is ideal for recursion, since the top element will be the most recently called function, which is what the computer needs to wrap up next. It’s a LIFO situation: the function that was called last (that is, most recently) is the function we need to complete first.

The next thing the computer does is pop the top element of the call stack, which currently is factorial(2):

The computer then completes its execution of factorial(2).

Now, the computer pops the next item from the stack. By this time, only factorial(3) is left on the stack, so the computer pops it and therefore completes running factorial(3).

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. Before it’s done…
2. factorial(2) is called second. Before it’s done…
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).

The factorial function is a calculation made based on recursion. The calculation is ultimately made by factorial(1) passing its result (which is 1) to factorial(2). Then factorial(2) multiplies this 1 by 2, yielding 2, and passes this result to factorial(3). Finally, factorial(3) takes this result and multiplies it by 3, computing the result of 6.

Some refer to this idea as passing a value up through the call stack; that is, each recursive function returns its computed value to its “parent” function. Eventually, the function that was initially called first computes the final value.

Stack Overflow

Let’s take a look back at the infinite recursion example from the beginning of the chapter. Recall that blah() called itself ad infinitum. What do you think will happen to the call stack?

In the case of infinite recursion, the computer keeps pushing the same function again and again onto the call stack. The call stack grows and grows until, eventually, the computer reaches a point where there’s simply no more room in its short-term memory to hold all this data. This causes an error known as stack overflow—the computer just shuts down the recursion and says, “I refuse to call the function again, because I’m running out of memory!”