Understanding Recursion With JavaScript

Introduction

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.

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) {
    ...
    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 is 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. Finally, the fourth line you answer and speak with the caller. When you are finished with the fourth caller, you hang up and pick up the third call. When you finish with the third call, you hang up and pick up the second call. When you finish with the second call, you hang up and pick up the first call. When you finish that call, you can finally put the phone down.

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. Last 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 sum the numbers from 1 to n. For example, if n = 4, it will sum 1 + 2 + 3 + 4.

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 zero. Zero has no parts, so our recursion can stop when we reach 0.

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

function sum(num){
    if (num === 0) {
        return 0;
    } else {
        return num + sum(--num)
    }
}

sum(4);     //10

This is what is happening at each step:

Go to sum(4).
Is 4 equal to 0? No. Put sum(4) on hold and go to sum(3).
Is 3 equal to 0? No. Put sum(3) on hold and go to sum(2).
Is 2 equal to 0? No. Put sum(2) on hold and go to sum(1).
Is 1 equal to 0? No. Put sum(1) on hold and go to sum(0).
Is 0 equal to 0? Yes. Evaluate sum(0).
Pick up sum(1).
Pick up sum(2).
Pick up sum(3).
Pick up sum(4).

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

sum(4)
4 + sum(3)
4 + ( 3 + sum(2) )
4 + ( 3 + ( 2 + sum(1) ))
4 + ( 3 + ( 2 + ( 1 + sum(0) )))
4 + ( 3 + ( 2 + ( 1 + 0 ) ))
4 + ( 3 + ( 2 + 1 ) )
4 + ( 3 +  3 ) 
4 + 6 
10

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.

Task

Implement the sum function using a loop instead of recursion.
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. This is an implementation for the function sum:

function sum(l){
    if (empty(l)) {
        return 0;
    } else {
        return car(l) + sum(cdr(l));
    }
}

The empty function returns true if the list has no elements. The car function returns the first element in the list. For example, car([1,2,3,4]) returns 1. The cdr function returns the list without the first element. For example, cdr([1,2,3,4]) returns [2,3,4]. What happens when we execute sum([1,2,3,4])?

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.

Task

Rewrite this sum function so that it uses a loop to sum each item in the list instead of recursion.
Define a function named length that takes a list as input and returns the number of elements in that list. You should not use JavaScript’s built-in length function. For example, length(['a', 'b', 'c', 'd']) should return 4. Write what happens at each step.

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 function remove, which takes an item and list as input and returns the list with the item removed. Only the first found item will be removed.

function remove(item, l){
    if (empty(l)) {
        return [];
    } else if (eq(car(l), item)) {
        return cdr(l);
    } else {
        return cons(car(l), remove(item, cdr(l)));
    }
}

remove('c', ['a', 'b', 'c', 'd'])       //[‘a’, ‘b’, ‘d’]

Here, the eq function returns true if both inputs are the same. The cons function takes an element and a list as inputs and returns a new list with the element added to the beginning of it.

We will be checking if the first item in the list is equal to the item we want to remove. If it is, remove the first element from the list and return the new list. If the first item is not equal to the item we want to remove, we take the first element in the list and add it to the recursive step. The recursive step will contain the list with the first element removed.

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?

remove('c', ['a', 'b', 'c', 'd'])
cons( ‘a’,  remove(‘c’, [‘b’, ‘c’, ‘d’]) )
cons( ‘a’ , cons( ‘b’, remove(‘c’, [‘c’, ‘d’]) ))
cons( ‘a’, cons( ‘b’, [‘d’] )
cons( ‘a’, [‘b’, ‘d’])
[‘a’, ‘b’, ‘d’]

In a situation when we need to build a list, we take the first element and add it to the recursive part of our list.

Task

Rewrite the remove function so that it uses loops instead of recursion to remove an element from a list.
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’] returns [‘a’, ‘b’, ‘d’]. Write what happens step by step.

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.

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.