Recursion in JavaScript for Beginners

Recursion is an incredibly useful and important topic in computer programming. Initially it can appear daunting and complex, but a well written recursive solution can not only be more elegant but also a more robust solution. However, like all tools in programming, there is a time and a place for it. With that, let’s dive in to recursion.

What is Recursion?

Recursion is the act of calling something upon itself. While this sounds confusing, it’ll become clearer as we walk through the steps. The idea is that we want to take a problem and slowly solve it by making use of the fact that each part of the problem has a similar structure. A great example of this is trying to find someone in a family tree. As we make our way down the tree we will be getting closer to who we want to find and the problem is getting smaller and smaller. In more recent cultural terms, the movie Inception is a decent example of recursion. A dream inside a dream, but for us we will have a function inside a function inside a function and so on, but yet they are all the same function.

When to use Recursion?

Recursion is ideally suited for solving problems that have an input that resembles itself even after a portion of it is solved. For example, below in Figure 1 we can see a simple tree. If we were to move from the top node down to one of the nodes below it, we would see the same thing, which is one node with three connected beneath it. So as we traverse the tree the input looks the same no matter where we are.

Figure 1. A simple family tree (data tree structure).

As stated earlier, recursion does have some drawbacks depending on the size of the input. If the problem is very large recursion is not an ideal solution for it. Additionally there are times when a recursive solution is not the clearest code and would result in code that could confuse other engineers. The key to remember with anything, is that its just a tool. There will be good times to use it and times not to. However, as a beginner you need to play around with the tool and understand it to be able to consider it a part of your tool kit. Now let’s look into how to implement a recursive solution.

The Steps of Recursion

  1. Determine that you do want to use recursion for your problem
  2. Define a base case
  • A base case can be thought as the indicator that your recursive function is done. Looking at a family tree it would be having gone through all members of the family.
  • The base case is crucial as it is what ends your recursive function, if it is improperly defined you could create a program that runs forever (an infinite loop).

3. Define our recursive case

  • This is what we want to be doing to our problem and will include calling the function back on itself.

4. Create a check for bad inputs

  • Good practice to ensure that our function does not run on something we don’t want it to.

Recursion in Practice

The most commonly shared example of recursion is the factorial, and I feel there are many resources out there already that have explained this well (Code Academy would be my recommendation). Anyways, I’d like something more removed from a mathematical mindset.

We will be using a family tree as our example. Think of Figure One above as our family with each node being a member of the family. In this case we will want to develop a program that will be looking to see how many people in our family have a given name and letting us know if at least three do. We want to use recursion here because over time the family tree will grow and we will want our function to be able to search through all of it. Again, as stated earlier the big reason to use recursion is that as our program walks down the tree, the input will look the same. We will walk through this conceptually and then the code will follow as we tease out more ways of using recursion.

The Solution in Concept

Base Case

Our base case will be once we have gone through all of the family members; so we won’t have to explicitly write it out. It can be thought as when there are no more children to go through. However, if this was the factorial, then our base case would be when we reached the number 0.

Recursive Case

We will want to check if the person (node as in one of the circles in Figure one) we are “currently at” in the program has the name we are looking for. If they do, we will increase our count of this name and then will want to recursively call our function on their descendants.

Termination Case

For the scope of this post, we will assume that we are given the proper inputs and that all nodes are properly defined. However, as you grow as a programmer, it’s an important step for your functions and programs to ensure that they are getting what they expected.

The Solution in Code

For simplicity we will be assuming a fair number of things for this to work. We will be assuming that we are given a node object that has a name property as well as a children property that stores all of its children in an array. These children stored in the array will be the same node object with a name property and an array of children. The code below is more for teasing out a conceptually understanding of recursion than actually functioning.

I’ll be solving the problem using two different approaches to recursion. Both have merit and an occasion to use them, and we’ll better understand after looking at the code.

Indirect Recursion Solution

// Define our recursive function taking a person (node object) and a name as an input
// The node can be thought of as our starting point, so for our family tree example
// It would be the oldest relative we know of
var familyCheck = function(person, name) {

// Define a count variable to keep track of the number of people with that name
var count = 0;

// Define our internal recursive function
var checkName = function(node, name) {
// Check if the current person's name is equal to our target name
if (node.name === name) {
// If they are, then we will increase our count
count++;
}
// Check the descendants of that person
for (var i=0; i<node.children.length; i++) {
// Recursively call the function on itself with a new input
checkName(node.children[i]);
}
};

// Invoke our recursive function on our given input parameters
checkName(person, name);

// Check the number of people with that name
if (count >= 3) {
return true;
} else {
return false;
}
};

Here we are using a function inside of a function to check the names. This solution utilizes a lexical scope to update a variable outside of itself. As we check each element we are updating the count variable and then at the end we will return that value. Our internal function will have access to the count variable due to its scope and it can increment it.

This methodology comes much easier to me however it does utilize a side effect in that our internal function updates something outside of itself. While this is not ideal, for this case it works well.

Direct Recursion Solution

This methodology does not use an internal function and instead only utilizes the overall function. This solution is actually going to solve a slightly different problem and we’ll talk over why after the code. The code below wants to just find out all the birthplaces of people with the same name. Anyways, let’s look at the code first and then we’ll talk through it afterwards.

// Define our recursive function to take a person and a name as inputs
var familyCheck = function(person, name) {
  // Create an array to store all the birthplaces
var placesOfBirth = [];

//Check if the current person's name is equal to our target name
if (person.name === name) {
// Add their birthplace to our array
placesOfBirth.push(person.birthplace);
}

// Check the descendants of that person
for (var i=0; i<person.children.length; i++) {
// For each descendant recursively call the function
var child = familyCheck(person.children[i], name);
// Update our birthplace array, this step is crucial
placesOfBirth = placesOfBirth.concat(child);
}

// Return the final resulting array
return placesOfBirth;
};

If you are wondering how that worked, then that’s fine. Part of the learning process is to run into things you don’t understand. Relax, and together we’ll figure it out.

The key to understanding the subroutine methodology lies in execution context. Execution contexts are another form of scope within JavaScript. David Shariff has a great blog on execution contexts here. The main takeaway for recursion is that when we call the function again it creates a new execution context. Figure two below tries to display what is happening. Try to answer what you think the arrows are conveying before reading the paragraph below.

Figure 2. A simple visual diagram of our recursive solution.

Each of the rectangles are an execution context. The function(person) is the original context of the very first time we invoke our recursive function. This will be the context that we will at the end return the final value from. So when we invoke the recursive function on the children nodes (and those children could have children and so on) we move into a new execution context. In the child’s execution context the placesOfBirth starts out being redefined, so yes it is empty again. But in that context we check that node (and its children) and then we return the placesOfBirth array. That is what is sent back to our original context.

The return arrow from the child’s execution context brings with it the child’s placesOfBirth array. So when we jump back to our original function(person) execution context the var child is defined as the child’s placesOfBirth array. That then gets added to our original function(person)’s placesOfBirth array by using concat. Then the for loop increments and repeats the process until we have gone through all of the children.

The big key here is that in our original context, placesOfBirth is not overwritten, but instead added to as each execution context returns its value. Herein lies the key to knowing when to use just the overall function or an internal function for your recursive function; what you want to output.

In our first example, we merely wanted to output a Boolean (true/false) if there were at least three people with that name in our family. So if we tried that with just the overall function we would only be returning a true/false from our recursive function, but in our second example we wanted to be grabbing more than that. So the output allowed us to utilize just the one function.

Recursion Conclusion

Recursion can be an incredibly powerful tool to solving some very elegant problems, but it does have many nuances to it. There are multiple ways to recursively solve a problem and which method to use largely depends on what you want to solve and return. So before coding, take the time to consider what you want your program to return. If you can answer that, then the road to your recursive solution should be much clearer. I hope this has helped clear up some of your questions, but if you have more feel free to ask in the comments. The key to understanding recursion is to try it out. So get out there and write some code!