Recursion

Recursion can be mind-bending but really it doesn’t rely on anything we haven’t learned yet.

We should be quite used to functions calling other functions.

Suppose we need to write an average function.

It should take an array of numbers as its argument and return their average.

How do we compute the average?

Sum the numbers in the array and divide the sum by the length of the array.

So let’s write that as directly as we can

const average = (ns) => {
  return sum(ns) / ns.length;
}

Assuming sum does what its name suggests, this is clearly correct.

Where does sum come from?

Who knows?

Maybe we’ve already written it.

Maybe we’ll write it next.

Maybe we’ll go to the function store and buy it.

Doesn’t really matter.

Building functions from smaller functions is one of the most powerful ways to manage complexity in our programs.

Why not write average like this?

const average = (ns) => {
  return ns.reduce((tot, n) => tot + n, 0) / ns.length;
}

Or this?

const average = (ns) => {
  let tot = 0;
  for (let i = 0; i < ns.length; i++) {
    tot += ns[i];
  }
  return tot / ns.length;
}

All three versions express the idea of “compute the average of an array of numbers by summing the numbers in the array and dividing by the array’s length”.

I’d argue that the original version expresses it most clearly by abstracting away the “summing the numbers” part.

But this does mean we need to be comfortable with abstraction: we need to be okay with assuming for the moment that sum does what we’d expect.

Helper functions

We can refer to sum as a “helper function” in the context of average.

It helps by doing part of the job, leaving the final putting together of the pieces to average.

Helper functions always solve only part of the problem.

If they solved the whole problem they’d be the function we’re trying to write.

Recursion is just defining a function that uses itself as a helper function

Consider factorial

n! = n × (n - 1) × (n - 2) … × 1

4! = 4 × 3 × 2 × 1 = 24

We want to write factorial

It should be a function that takes a single non-negative integer, n, as its argument and returns n!.

Following mathematical convention, factorial(0) should return 1.

Note that if 0! is 1, for all n > 0 the definition of factorial:

n! = n × (n - 1) × (n - 2) … × 1

could also be written:

n! = n × (n - 1)!

So let’s pull out the ACME catalog, and order up a helper function

factorialOfNMinusOne

that for any n > 0 can compute the factorial of n - 1.

Now implement factorial using our helper function:

const factorial = (n) => {
  if (n === 0) { // Can't call factorialOfNMinusOne with 0.
    return 1;
  } else {
    return n * factorialOfNMinusOne(n);
  }
}

Does this work?

Just like defining average in terms of sum, if factorialOfNMinusOne works as advertised, this should be a correct implementation of factorial that works for for any non-negative integer n.

Sadly ACME doesn’t sell functions

So we’ve got to write factorialOfNMinusOne ourselves.

Luckily, we’ve now got a working factorial function so we can define factorialOfNMinusOne like this:

const factorialOfNMinusOne = (n) => {
  return factorial(n - 1);
}

Since factorial works for all numbers greater than or equal to zero, and factorialOfNMinusOne is only required to work for numbers greater than zero this should always work.

In fact, factorialOfNMinusOne is so simple we might as well write it in-line:

const factorial = (n) => {
  if (n === 0) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}

Wait, is this us?

Nope

It seems circular since factorial calls itself.

But it’s more of a spiral, since each call to factorial is solving a “smaller” problem and eventually, it bottoms out at the case where n is 0.

This is just like how the helper function sum only solved part of the larger problem of computing the average.

The call to factorial(n - 1) is only solving part of the larger problem of factorial(n).

The smallest problem—when n is 0—is handled specially.

All recursive functions have this same basic structure.

• A base case, which is the smallest problem to be solved and which can be answered directly.

• A recursive case, where the function calls itself with a smaller problem and then uses the answer it gets to produce the answer to the larger problem.

Why though?

Factorial could be solved non-recursively, a.k.a. “iteratively”:

const factorial = (n) => {
  let answer = 1;
  for (let i = 1; i <= n; i++) {
    answer *= i;
  }
  return answer;
}

But it’s maybe easier to see that the recursive solution is correct since it’s basically a translation of the mathematical definition.

Other problems are even more inherently recursive, such as searching a tree of values for a specific value.

Find if a given item is in a tree:

const inTree = (tree, item) => {
  if (isLeaf(tree)) {
    // Base case: we're at a leaf node
    return tree === item
  } else {
    // Recursive case: check both branches in the tree
    return (
      inTree(tree.left, item) ||
      inTree(tree.right, item)
    );
  }
};

We could write this iteratively but becuase of the branching it’s not just a simple for loop.

Similarly, searching the virtual tree of possible positions in a board game:

const canWin = (position, player) => {
   if (gameOver(position)) {
     return winner(position) === player;
   } else {
     const nexts = possibleNextPositions(position);
     for (let i = 0; i < nexts.length; i++) {
       if (canWin(nexts[i], player)) {
         return true;
       }
     }
     return false;
   }
 };

How to write a recursive function

Step 1: What are we recursing on?

In simple cases this is just whatever the argument to the function is. If the function operates on numbers we’re recursing on numbers. If it takes an array, we’re recursing on an array. If it’s some tree structure, it’s that.

If the function takes more than one argument, probably one of them is the thing we’re recursing on.

But not always. In the problem set we’ll be doing soon, there’s at least one problem that requires recursing on both its arguments.

Step 2: Identify the base case

What is the smallest version of the problem? If we’re recursing on numbers it’s probably 0 or 1. If we’re recursing on an array or string, it’s probably the empty array or empty string.

But the real test of whether something is the base case is that we can determine the answer without solving a yet smaller problem.

Step 3: Handle the base case

Start by writing the if statement that detects the base case and returns the appropriate answer. For instance

const sumOfArray = (ns) => {
  if (ns.length === 0) {
    return 0; // The sum of no numbers (an empty array) is 0.
  }
  // ...
}

Step 4: Identify how to shrink the problem

The recursive case will contain a call to the function but with a “smaller” version of the problem, i.e. one step closer to the base case.

For instance, if the base case is an empty array, we shrink the problem by making an array that is one item smaller.

Step 5: Write the recursive case

Write the recursive case, combining the part of the problem not handled by the recursive call with the result of the recursive call.

const sumOfArray = (ns) => {
  if (ns.length === 0) {
    return 0; // The sum of no numbers (an empty array) is 0.
  } else {
    return ns[0] + sumOfArray(ns.slice(1));
  }
}

Recursion visualization

If you want to walk through how a recursive function works, stey by step, you might enjoy this visualization.

Problem set

Have fun!