Dijkstra was right — recursion should not be difficult

“ …and discovered to my surprise that 10 % of my audience had the greatest difficulty in coping with the concept of recursive procedures. I was surprised because I knew that the concept of recursion was not difficult.” — Dijkstra’s keynote address of 1 March 1999

Nearly every programming language offers a set of control flow tools: conditional constructs like if…else or switch…case, and looping mechanisms such as for and while. For most newcomers, iterative constructs are the first ones they encounter.

Yet there exists another control structure of equal importance: recursion. It stands as one of the foundational concepts in computer science, yet it is frequently perceived as one of the more challenging topics for learners. Textbooks tend to postpone its introduction well past the coverage of loops and conditionals.

Given the flood of online queries about why recursion feels so elusive, one might conclude it's an inherently advanced subject. That doesn't need to be the case.

Admittedly, spotting the recursive pattern in a problem and crafting a solution takes some intuition, but this skill can be cultivated. This article aims to unpack several ideas and techniques that will aid you in tackling recursive exercises.

Why opt for recursion?

You've likely come across the quip that to comprehend recursion, you must first comprehend recursion. This aligns with the standard description of recursion as a function invoking itself.

Such a description might suggest that these calls spiral into an endless loop, but a correctly constructed recursive solution is never infinite. The reason is that each recursive call never tackles the exact same problem as the original; rather, it handles a reduced version of it. Eventually, this reduced version becomes trivial to solve, and that's precisely when the recursion halts.

This brings us to the primary reason for employing recursion: use it to simplify the problem at hand.

Let's illustrate this with an example. Imagine you need to compute the total of all numbers in an array that may contain nested sub-arrays. If a function receives the following structure:

[1,[11,42,[8, 1], 4, [22,21]]]

it should return the combined sum of every element:

1+11+42+8+1+4+22+21 = 110

The key is to pinpoint a simpler sub-problem, solve that, and then express the original problem in terms of that simpler case. Apply recursion repeatedly until you hit the easy case, and from there, all the intermediate steps resolve themselves back up to your initial problem.

The most basic version of this problem is an array without any nested arrays. For such an array, the summing function might be:

function sum(a) {
    let result = 0;

    for (let i = 0; i < a.length; i++) {
        result += a[i];
    }
    return result;
}

assert.equal(sum([1, -5, 100]), 96);

Now we have a sum function that accepts an array and returns the total of its elements. Let's tackle the original, more complex version. The challenge is that certain elements might themselves be arrays, whereas our current implementation assumes every element is a number. So we merely need to verify whether each element is an array; if it is, we already possess the sum function to add up all the numbers within that sub-array. Let's adjust our function:

function sum(a) {
    let result = 0;

    for (let i = 0; i < a.length; i++) {
        if (Array.isArray(a[i])) {
            result += sum(a[i])
        } else {
            result += a[i];
        }
    }
    return result;
}

assert.equal(sum([1,[11,42,[8, 1], 4, [22,21]]]), 110);

That's all there is to it. We first cracked the simpler case and then leveraged that solution to handle the tougher one. An iterative approach is possible here, but it's far messier because you'd have to nest for loops without knowing how deep they go. That uncertainty about nesting depth is a telltale sign of a recursive problem, suggesting that recursion is the right path.

Beyond simplifying problems, recursion offers another valuable trait: the ability to backtrack. Tasks that demand backtracking typically involve traversing trees or graphs, like navigating a maze. Such problems are solved incrementally, one step at a time. The general pattern is:

1. If the current step equals the solution, return the result.
2. If it doesn't, check for any unexplored paths from here.
3. If paths remain, pick one and follow it to test for a solution.
4. If no paths are left, backtrack to a previous position.

Let's see this in action. Suppose we have the following tree:

It's structured as nodes with child references:

let tree = {
    name: 'A',
    value: 4,
    children: [
        {
            name: 'B', value: 7,
            children: [{name: 'C', value: 9, children: []}]
        },
        {
            name: 'D', value: 11,
            children: [{name: 'E', value: 9, children: []}]
        },
        {name: 'F', value: 55, children: []},
        {
            name: 'G', value: 65,
            children: [
                {name: 'H', value: 21, children: []},
                {name: 'I', value: 33, children: []}
            ]
        }
    ]
};

Our goal is to locate a node holding the value 21.

Here's the step-by-step plan:

1. Start by examining node A.
2. If it doesn't match, move on to B, then C.
3. None of these have the right value, and we're at a dead end, so we backtrack to A.
4. Next, we inspect D and E. Still no match.
5. Backtrack again. Check F.
6. Backtrack. Test G. Still not it.

But options remain. Finally, we reach H, and it's the node we've been seeking.

The implementation is quite straightforward:

function find(node, value) {
    if (node.value === value) {
        return node;
    } else {
        for (let i = 0; i < node.children.length; i++) {
            let found = find(node.children[i], value);
            if (found !== null) {
                return found;
            }
        }

        return null;
    }
}

assert.equal(find(tree, 21).name, 'H');

Crafting a solution

A typical pitfall for novices is attempting to visualize what happens inside the recursive call, instead of simply trusting it to produce the correct outcome. In the nested array example, for the solution:

if (Array.isArray(a[i])) {
    result += sum(a[i])
    ...
}

don't try to trace what unfolds when the sum function runs. That's not a productive way to approach recursion. Instead, trust that it correctly sums all elements within the array a[i]. Additionally, refrain from viewing a recursive program as a sequence of execution steps or trying to mentally reconstruct the entire call tree. For complex problems, that's both arduous and unhelpful for devising a solution.

Begin by considering how the original problem can be broken down into a simpler version along with some supplementary actions. Pinpointing that simpler version is often the toughest part of solving a recursive problem. For straightforward cases like those above, it's obvious, but for more intricate challenges, identifying the pattern takes practice. The more you practice, the sharper your eye becomes.

Once you've singled out the simpler problem, the next step is to determine the most basic case your function must handle—the base case. This is typically expressed as a condition that halts the recursion. In our earlier examples, it appeared as a loop checking for remaining elements in an array (sum) or remaining children in a node (find). Sometimes, with easy problems, the simpler sub-problem coincides with the base case, but that's not always true, as seen in the classic "Tower of Hanoi":

You're given three rods and several disks of varying sizes that can slide onto any rod. The disks start stacked in ascending order of size on one rod. Your goal is to move the entire stack to Tower 3, but you can only move one disk at a time and cannot place a larger disk on top of a smaller one.

The key insight you need to spot is this:

1. Shift n-1 disks to the auxiliary rod.

2. Move the largest disk from the source to the target rod.

3. After that, transfer the n-1 disks from the auxiliary rod to the target rod.

The crucial point is to avoid thinking through the specific moves for the n-1 disks; instead, presume they've been moved already, freeing you to shift the largest disk and then relocate the rest. Let's codify this:

function move(n, src, aux, dest) {

    // move all disks but the last from source to auxiliary rod,
    // that's why aux and dest rods are swapped in a function call
    // so that aux rod becomes the destination
    move(n - 1, src, dest, aux);
    
    // move the last disk from source to destination rod
    dest.push(src.pop());
    
    // move the remaining disks from auxiliary to target rod,
    // that's why aux and src rods are swapped in a function call
    // so that auxiliary rod becomes the source
    move(n - 1, aux, src, dest);
}

Now that we've identified the simpler sub-problem, we need to pin down the base case. It's fairly clear:

If only one disk remains, move it directly to the target rod:

function move(n, src, aux, dest) {
    if (n === 1) {
        dest.push(src.pop());
    } else {
        move(n - 1, src, dest, aux);
        dest.push(src.pop());
        move(n - 1, aux, src, dest);
    }
}

This base case terminates the recursion, and note it's distinct from the simpler sub-problem that solves the original challenge.

Now, put these concepts to the test with the following exercises:

1. Sum of nested arrays

Write a function that totals all numbers in an array that may have nested sub-arrays. Avoid using loops.

2. Generating binary strings

Write a function that produces every possible combination of 1 and 0 for n bits. For instance, with 2 as the bit count, it should yield four results: 00,01,10,11. Mathematical operators are off-limits.

As you formulate your approach, focus on identifying the simpler sub-problem and the base case, rather than mapping out every execution step. Additionally, consider placing yourself at an intermediate stage: what single action would you take next to advance toward the solution?

Solutions and explanations can be found at the end of this piece.

Optimizing tail calls

The term call stack is something you’ve likely encountered, especially when debugging—it’s how you see the chain of function calls that led to an error. For instance, if you have code like this in index.js:

function a(n) {
    let a = 1;
    return a + n;
}

function b(n) {
    let b = 5;
    let value = a(n);  // line B
    return b + value;
}

function c() {
    let c = 3;
    let v = b(c);  // line C
    console.log(v);
}

c();  // line A

and set a breakpoint inside a, the call stack displayed would resemble this:

a() (return to: {b(): B}, locals: {a=1, n=3})
b() (return to: {c(): C}, locals: {b=5, n=3})
c() (return to: {index.js: A}, locals: {c=3, v=undefined})

This tells you that a was invoked by b, and b by c—hence the name “call stack,” a stack of function invocations. Each item on this stack is called a stack frame, which contains, among other details, local variables and the return address (where execution should resume after the function completes). Crucially, the stack’s capacity is bounded—the number and size of frames aren’t infinite. If you keep calling functions, you’ll eventually trigger a stack overflow error. This limit isn’t fixed; it changes across environments and depends on how large each function’s frame is.

Because recursive functions invoke themselves repeatedly, they carry a real risk of hitting a stack overflow. Consider this straightforward recursive factorial:

function fact(n) {
    if (n === 0 || n === 1) {
        return 1;
    }
    return n * fact(n - 1);
}

Passing a sizable number like 100 000 will almost certainly cause an error in most settings. This fact—that the recursive way to compute factorials is generally avoided as a recursion example—makes sense, since a loop can handle it more efficiently. Beyond the overflow danger, this recursive version also slows things down by consuming additional stack frames and, therefore, extra memory.

Still, this pattern is the go-to approach in many functional languages, such as Lisp and Scheme. So, how do they dodge these pitfalls? The trick lies in tail-call optimization. Let’s revisit the earlier stack example, but refactored:

function a(n, p) {
    let a = 1;
    return a + n + p;
}

function b(n) {
    let b = 5;
    return a(n, b);
}

function c() {
    let c = 3;
    let v = b(c);  // line C
    console.log(v);
}

c();  // line A

Now, it’s evident there’s no point in allocating a stack frame for b, since its only job is to call a with no follow-up work. The compiler catches this and skips creating a frame for b. The optimized stack now looks like this:

a() (return to: {c(): C}, locals: {a=1, n=3, p=5})
c() (return to: {index.js: A}, locals: {c=3, v=undefined})

Compare the original and refactored versions of b:

// without tail-call optimization
let value = a(n);
return b + value;

// with tail-call optimization
return a(n, b);

The key change is that nothing happens after a returns. Let’s adjust our factorial function to benefit from this optimization:

function fact(acc, n) {
    if (n === 1) {
        return acc;
    } else {
        return fact(acc * n, n - 1);
    }
}

Notice that instead of waiting for the recursive call to finish and then doing the math, we compute the intermediate result first and pass it into the next recursive call. In the non-tail version, you make all your recursive calls first, then use their return values for further calculations. This means you don’t get your final answer until every recursive step has returned.

To switch to a tail-recursive design, you do your calculations up front, then make the recursive call, handing off the results from the current step to the next. The final recursive call simply returns the accumulated value once the base case is met. Essentially, the return value from each recursive step equals the return value from the next one. As a result, once you’re ready to move to the next recursive call, the current stack frame is no longer needed.

In some functional languages, tail-call optimization can also be achieved via continuation-passing style (CPS), also known as callbacks. With callbacks, return statements become unnecessary, enabling the compiler to streamline recursive calls. While JavaScript handles callbacks well, it doesn’t currently support tail-call optimization through CPS.

Approaches to the problems

So, let’s tackle the first challenge:

Write a function that sums all numbers in an array that can have nested sub-arrays. Do not use loops.

We start by focusing on a simpler version—an array with no nested elements. Let’s ask ourselves the usual questions:

1. What is the simpler problem? It’s when I have the sum of n-1 elements and just need to add the current element to that total.
2. What is the base case? It’s when there are no elements left—return 0.

Here’s the implementation:

function sum(a, i) {
    if (i < 0) {
        return 0;
    } else {
        return a[i] + sum(a, i - 1);
    }
}
let input = [1, 2, 0, 3];
assert.equal(sum(input, input.length-1), 6);

That solves the easy case. Now, we need to handle nested arrays. We can check whether each element is an array, and if so, call the sum function on it. Just be sure to grab the sum from the sub-array and include it in the final result. This gives us the full solution:

function sum(a, i) {
    if (i < 0) {
        return 0;
    }

    let current = a[i];

    if (Array.isArray(a[i])) {
        current = sum(a[i], a[i].length - 1);
    }

    return current + sum(a, i - 1);
}

let input = [1, 2, [1, 2], 3, [5]];
assert.equal(sum(input, input.length - 1), 14);

Now, let’s look at the second problem:

Write a function that generates all possible combinations of 1 and 0 for n bits. For example, if the function receives 2 as the number of bits, it should produce the following 4 combinations: _00,01,10,11_. You cannot use any mathematical operators.

What’s the simplest scenario here? We just need strings for a single bit, giving us 1 and 0. So, if the number of bits is 1, we output both. Let’s sketch that out, assuming a global a array:

var a = [];

function binary(n) {
    if (n === 1) {

        a[n - 1] = 0;
        console.log(a.join(''));

        a[n - 1] = 1;
        console.log(a.join(''));
    }
}

This version has a redundant console.log, so we can tidy it up by moving the logging to the end, only when no bits remain. Here’s the improved code:

var a = [];

function binary(i) {
    if (i === 0) {
        console.log(a.join(''));
    } else {
        a[i - 1] = 0;
        binary(i - 1);
        a[i - 1] = 1;
        binary(i - 1);
    }
}

Now, consider what combinations look like for 2 bits:

binary(2); // outputs 00, 10, 01, 11

We start with no bits assigned. We set the n bit to 0, then move to the n-1 bit. This continues until all bits are set. At that point, we print the combination and backtrack one level. Then, we flip the n bit to 1. At every stage, the function focuses solely on assigning the current bit and invoking itself to manage the remaining bits.

That’s exactly what our implementation does for one bit. As it turns out, just by adjusting the base case, we’ve found a solution that scales to any number of bits.