A Common-Sense Guide to Data Structures and Algorithms in JavaScript, Volume 1

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:

function recurse(n) {
  if (n < 0) { return; }

  console.log(n);
  recurse(n - 1);
}

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, ​Recursively Recurse with Recursion​. You learned that each time a function recursively calls itself, ...