A Common-Sense Guide to Data Structures and Algorithms

Chapter 9Recursively Recurse with Recursion

You’ll need to understand the key concept of recursion in order to understand most of the remaining algorithms in this book. Recursion allows for solving tricky problems in surprisingly simple ways, often allowing us to write a fraction of the code that we might otherwise write.

But first, a pop quiz!

What happens when the blah() function defined below is invoked?

function blah() {
  blah();
}

As you probably guessed, it will call itself infinitely, since blah() calls itself, which in turn calls itself, and so on.

Recursion is the official name for when a function calls itself. While infinite function calls are generally useless—and even dangerous—recursion is a powerful tool that can be harnessed. ...