Algorithms 101: Learn Recursion with Nesting Dolls in JavaScript

Noob v. Algorithms #12, another take on recursion

In my last post, I wrote about recursion in Ruby, using an example of the Princess and the Pea. If you understood that and want to try a more complex example, let’s look at a different example in JavaScript.

First things first: a recursion is a function that calls itself. A classic use for recursion is traversing a file tree.

Nesting dolls

Opening up folders in a file tree, and folders inside those folders, is a bit like opening up nesting dolls.

Let’s say a friend gives you a set of nesting dolls. Inside the smallest doll that opens you will find one of two things: a diamond(!) or nothing.

How would you write instructions to find whether your set has a diamond or nothing?

Steps for searching

Open doll.
If you find a diamond, your work is done!
If you find a doll, open it.
If you find a diamond, your work is done!
If you find a doll, open it.
If you find a diamond, your work is done!
If you find a doll …

There’s a pattern here. Let’s condense:

Open doll
If you find a diamond, your work is done! Skip step 3.
If you find a doll, start again from Step 1.

Here’s what our nesting dolls would look like in code.

The outside doll is doll1; when you open it up, you find doll2 etc. Until finally, you open up doll5 and find a diamond.

Base case, a much-needed exit!

The most important part of a recursion is the base case — the condition, when met, stops the function from calling itself. Without a base case, a recursive function keeps going in an infinite loop.

The easiest way to define a base case is: when should I stop looking?

In our example, we need two base cases. We want to stop looking if:

we finish opening all the dolls without finding a diamond, or
we finish opening all the dolls and we do find the diamond.

In code:

Lines 16–17 cover the case where we opened all the dolls without finding the diamond. (How do we know if we’ve reached the last doll? Because the last doll contains either nothing or a diamond. If we find a doll with either, it must be the last doll.)

Lines 18–19 cover the case where we open a non-empty doll and find a diamond.

Recursion

Now let’s write our search instructions.

Let’s unpack that.

Every time we open a doll, we want to know — is there another doll (array) inside? We use line 21 to check if the current doll is an array.

If so, we pass that doll (the array called current) back into the function and start all over again.

Important: we don’t just call the function again; we say that we want to return the result of that function. The result is defined in the base cases. If we did not include “return result” at the beginning of line 22, we wouldn’t return anything.

Let’s look at the whole function:

The first time through the loop, we check to make sure we’re actually looking at something. We’re looking at doll1, which is an array with a length of 1.

So we skip to line 20, and iterate through the contents of doll1. We find doll2, pass that back in, check to see if it is empty or if its first item is “diamond”. Neither is true, so we go back to line 20, iterate over the contents and find doll3. And so on …

Finally, we reach the last doll, doll5. When we feed it back into the function, it meets the condition for a base case on line 16. That is, the first item inside of doll5 is “diamond”!

So we return result = “found!". Now that we have a result, line 22 finally has something to return! So our function ends.

You can play with this code here on repl.it. Try changing doll5 to [] to see what happens when there’s no diamond.

Need a gentler introduction to recursion?

Try my previous post on recursion, Algorithms 101, #11: Princesses, Peas & Recursion in Ruby.

Next: Algorithms 101, #13: Pascal’s Triangle in JavaScript