The Hidden Cost of Recursion

We’ve dealt quite a bit with recursive algorithms in this book. Let’s look at a simple recursive function:

This function accepts a number n and counts down to 0, printing each decrementing number along the way.

It’s a straightforward bit of recursion and seems harmless. Its speed is O(N), as the function will run as many times as the argument n. And it doesn’t create any new data structures, so it doesn’t seem to take up any additional space.

Or does it?

I explained how recursion works under the hood back in Chapter 10, . You learned that each time a function recursively calls itself, an item is added to the call stack so that the computer can come back to the outer function once the inner function is complete.

If we pass the number 100 into our recurse function, it would add recurse(100) before proceeding to execute recurse(99). And it would then add recurse(99) to the call stack before executing recurse(98).

The call stack would be at its peak when recurse(-1) is called, and there would be 101 items in the call stack, from recurse(100) down to recurse(0).

Now, even though the call stack will eventually get unwound, we do need enough memory to store these 101 items for at least some period of time. It emerges, then, that our recursive function takes up O(N) space. In this case, N is the number passed into the function; if we pass in the number 100, we need to temporarily store about 100 function calls in the call stack.

An important principle emerges from all of this: a recursive function takes up a unit of space for each recursive call it makes. This is the sneaky way recursion can gobble up memory; even if our function doesn’t explicitly create new data, the recursion itself adds data to the call stack.

To properly calculate how much space a recursive function takes, we always need to figure out how big the call stack would be at its peak.

For our recurse function, the call stack will be about as large as whatever number n is.

At first, this may seem a bit trivial. After all, our modern computers can handle a few items on the call stack, right? Well, let’s see.

When I pass in the number 20,000 into the recurse function on my sleek, up-to-date laptop, my computer cannot process it. Now, 20,000 doesn’t seem like a very large number. But this is what happens when I run recurse(20000):

My computer prints the numbers from 20000 until 19005 and then terminates with the message:

Because the recursion lasted from 20000 until about 19000 (I’m rounding 19005 down), we can figure out that the call stack reached a size of about 1,000 when the computer ran out of memory. It turns out my computer will not tolerate a call stack that contains more than 1,000 items.

This is a huge limitation on recursion, as I can’t use my beautiful recurse function on a number greater than 1,000!

Let’s contrast this to a simple loop approach:

This function accomplishes the same goal using a basic loop instead of recursion.

Because this function doesn’t use recursion, and doesn’t take up any additional memory, it can process a huge number without ever causing the computer to run out of space. The function may take some time on huge numbers, but it’ll get the job done without giving up prematurely as the recursive function did.

With this in mind, we can now understand why Quicksort is said to take up O(log N) space. Quicksort makes O(log N) recursive calls, so at its peak has a call stack that is the size of log(N).

When we can implement a function using recursion, then, we need to weigh recursion’s benefits against its drawbacks. Recursion allows us to use the “magical” top-down mindset, as you looked at in Chapter 11, , but we also need our function to get the job done. And if we’re processing a lot of data, or even just a number like 20,000—or even 1,000—recursion may not cut it.

Again, this isn’t to discredit recursion. It just means we need to weigh all the pros and cons of each algorithm in every situation.