Understanding Recursion With JavaScript

Some problems are more naturally solved using recursion. For example, a sequence like the Fibonacci sequence has a recursive definition. Each number in the sequence is the sum of the previous two numbers in the sequence. Problems that require you to build or traverse a tree-like data structure can also be solved with recursion. Training yourself to think recursively will give you a powerful skill to attack such problems. 

In this tutorial, I will go through several recursive functions step by step to see how they work and show you techniques you can use to systematically define recursive functions.

Contents:

• What Is Recursion?
• Recursion With Numbers
• Recursion With Lists
• Building Lists
• Tail Recursion
• Review

What Is Recursion?

A recursively defined function is a function that is defined in terms of a simpler version of itself. This is a simplified example:

function doA(n) {
    ...
    if (n > 0) {
        doA(n-1);
    }
}

To understand how recursion works conceptually, we will look at an example that has nothing to do with code. Imagine you are responsible for answering phone calls at work. Since this is a busy company, your phone has multiple phone lines so you can juggle multiple calls at the same time. Each phone line has a button on the receiver, and when there is an incoming call, the button will blink. Today, when you arrive to work and turn the phone on, there are four lines blinking at once. So you get to work answering all of the calls.

You pick up line one and tell them, “Please hold.” Then you pick up line two and put them on hold. Next, you pick up line three and put them on hold, and so on. Finally, when you are done with each call, you go back to the previous caller, finish that call, and hang up.

Each of the phone calls in this example is like a recursive call in a function. When you get a call, it is put on the call stack (in code speak). If you cannot complete a call right away, you put the call on hold. If you have a function call that can’t be evaluated immediately, it stays on the call stack. When you are able to answer a call, it is picked up. When your code is able to evaluate a function call, it is popped off the stack. Keep this analogy in mind as you look over the following code examples.

Recursion With Numbers

All recursive functions need a base case so they will terminate. However, just adding a base case to our function does not prevent it from running infinitely. The function has to have a step to bring us closer to the base case. This is the recursive step. In the recursive step, the problem is reduced to a smaller version of the problem.

Suppose you have a function that will multiply all the numbers from 1 to n. This is called the factorial function, and we write it as n!. For example, 4!, is 1 * 2 * 3 * 4 = 24. 

First, we determine the base case. Finding the base case can also be thought of as finding the case where the problem can be solved without recursion. In this case, it is when n equals one.  

At each step, you will subtract one from the current number. What is the recursive case? The recursive case is the function fact called with the reduced number.

function fact(num) {
    if (num === 1) 
		return 1;
	else 
		return num * fact(--num);
}

fact(4); //24

• Call fact(4).
• Is 4 equal to 1? No. Put fact(4) on hold and go to fact(3).
• Is 3 equal to 1? No. Put fact(3) on hold and go to fact(2).
• Is 2 equal to 1? No. Put fact(2) on hold and go to fact(1).
• Is 1 equal to 1? Yes. Return 1.
• Pick up fact(2) and return 2 * fact(1) is 2.
• Pick up fact(3) and return 3 * fact(2) is 6.
• Pick up fact(4) and return 4 * fact(3) is 24.

This is another way to view how the function is processing each call:

fact(4)
4 * fact(3)
4 * ( 3 * fact(2) )
4 * ( 3 * ( 2 * fact(1) ))
4 * ( 3 * ( 2 * 1 ) )
4 * ( 3 * 2 )
4 * 6
24

The argument should change in the recursive case and bring you closer to the base case. This argument should be tested in the base case. In the previous example, because we are subtracting one in the recursive case, we test if the argument equals zero in our base case.

Challenge

1. Implement the sum function using a loop instead of recursion.
2. Create a function that multiplies two numbers recursively. For example, multiply(2,4) will return 8. Write what happens at each step for multiply(2,4).

Recursion With Lists

Recurring on a list is similar to recurring on a number, except that instead of reducing the number at each step, we are reducing the list at each step until we get to an empty list. 

Consider the sum function that takes a list as input and returns the sum of all of the elements in the list:

function sum(l) {
    if (l.length === 0) {
        return 0;
    } else {
        return l[0] + sum(l.slice(1));
    }
}

First, you check whether the array of numbers is empty. If it is, then you return 0; otherwise, you return the first element of the array plus the sum of all elements except the first. That is where the recursion comes in. Because sum calls sum when the array is longer than zero, the function is recursive. Here is a representation of what is happening at each step.

sum([1,2,3,4])
1 + sum([2,3,4])
1 + ( 2 + sum([3,4]) )
1 + ( 2 + ( 3 + sum([4]) ))
1 + ( 2 + ( 3 + ( 4 + sum([]) )))
1 + ( 2 + ( 3 + ( 4 + 0 ) ))
1 + ( 2 + ( 3 + 4 ) )
1 + ( 2 + 7 )
1 + 9
10

When recurring on a list, check if it is empty. Otherwise, do the recursive step on a reduced version of the list.

Challenge

While recursion works here, loops can be faster and work better in cases like this. Rewrite this sum function so that it uses a loop to sum each item in the list instead of recursion.

Building Lists

In the last example, we were returning a number. But suppose we wanted to return a list. That would mean that instead of adding a number to our recursive step, we would need to add a list. Consider the remove function, which takes an item and list as input and returns the list with the item removed. Only the first found instance will be removed.

function remove(item, l) {
    if (l.length === 0) {
		return [];
	} else if (item === l[0]) {
		return l.slice(1);
	} else {
		return [l[0], ...remove(item, l.slice(1))];
	}
}

console.log(remove("c", ["a", "b", "c", "d"])); //[‘a’, ‘b’, ‘d’]

We will keep removing elements until we reach our base case, which is an empty list. An empty list means we have traversed all the items in our list. What does remove('c', ['a', 'b', 'c', 'd']) do?

["a", ...remove("c", ["b", "c", "d"])];
["a", ...["b", ...remove("c", ["c", "d"])]];
["a", ...["b", ...remove("c", ["d"])]];
["a", ...["b", ...["d"]]];
["a", ...["b", "d"]];
["a", "b", "d"];

Challenge

1. Alter the remove function so that it removes all occurrences of an item from a list. For example, remove("c", ["a", "b", "c", "d", "c"] should return ["a", "b", "d"].
2. Simplify the remove function to use JavaScript’s built-in array method filter.

Tail Recursion

Tail recursion is a form of recursion that allows the compiler to perform tail call optimization (TCO) to prevent many of the performance pitfalls normal recursion has. Additionally, tail recursion solves the problem of having a maximum depth of function calls. However, you have to write your functions a certain way for this to work.

Tail recursion works with functions that call the recursive function at the end of the function. For example, here is the sum() function refactored to use tail recursion:

function sum(l, n) {
    if (l.length === 0) {
        return n || 0;
    } else {
        n ??= 0;
        n += l[0];
        return sum(l.slice(1), n);
    }
}

As you can see, sum() is the entire return value, so the runtime can safely discard the outer function and just return the result from the inner function. However, many people get tripped up by things like this:

function notTailRecursive(n) {
    ...
    return notTailRecursive(n)+1
}

You might think that this uses tail recursion, as the recursive function is called at the end. However, it does not. That is because JavaScript has to return to the outer function to add one. One way you could rewrite it is to pass the +1 inside the arguments, so then the inner function can do that computation.

Not all browsers currently support tail call optimizations, but it is in the ES standard, so we might see more support for it in the future. Additionally, it is often a good practice, as it usually isolates changes to the arguments of the function.

Challenge

Refactor one of the example recursive functions in this post to be tail recursive.

Review

There are three parts to a recursive function. The first is the base case, which is the terminating condition. The second is the step to get us closer to our base case. The third is the recursive step, where the function calls itself with the reduced input. 

Recursion is like iteration. Any function that you can define recursively can also be defined using loops. Other things to consider when using recursion are recurring on nested lists and optimizing your recursive calls.

You can refactor recursive functions to be tail recursive, which can offer performance benefits.

A great resource to continue learning about recursion is the book The Little Schemer. It teaches you how to think recursively using a question-and-answer format.

This post has been updated with contributions from Jacob Jackson. Jacob is a web developer, technical writer, freelancer, and open-source contributor.