Functions Calling Themselves

Recursive Functions

Todd Motto by Todd Motto Google Developer Expert Icon Google Developer Expert
JavaScript Icon

Learn JavaScript the right way

Premium JavaScript courses to skyrocket your skills to the top.

5x Courses: Basics, Masterclass, HTML5 APIs, DOM, Testing with Jest.

A recursive function is simply a function that calls itself. This is usually to repeat the same task, perhaps on a nested data structure.

The technique is referred to as “recursion” and is a common functional programming concept.

Recursion works best when strict functional programming rules are followed, by using pure functions.

This makes them easily testable and predictable.

So, how and where can we use recursion? Many examples you’ll find online provide odd use cases that teach you the idea behind recusion, but without any practical examples.

Taking our cart variable, let’s assume that we’ve added a 'Coffee' that has a price, but also comes with some added extras that are charged individually:

const cart = [
  {
    name: 'Coffee',
    price: 399,
    extras: [
      { 
        name: 'Extra Shot',
        price: 99
      },
      {
        name: 'Vanilla Syrup',
        price: 149
      }
    ]
  }
];

We need to calculate the total price by adding together each price property.

This gives us an interesting challenge, and can be solved in many ways.

We could use imperative operations alongside traditional for loops, or a declarative approach with more modern techniques like Array.prototype.reduce.

Let’s first explore an imperative solution, whereby we’ll tell the program what to do, how to work it out, and then refactor to a declarative solution - and finally a recursive function.

let total = 0;

for (let i = 0; i < cart.length; i++) {
  const item = cart[i];
  total += item.price;
  if (item.extras) {
    for (let z = 0; z < item.extras.length; z++) {
      const extra = item.extras[z];
      total += extra.price;
    } 
  }
}

console.log(total); // 647

What a mess. If you had to take a few moments to figure out what was going on here, that’s exactly the problem.

First we create a variable to store the total, then a nested for loop, whilst mutating the total variable each time as we continue the loop.

A big issue I have with this approach is that nothing is really being “kept” in memory, and the total variable sees multiple mutations as the loop progresses, making it even more challenging to debug later as we’re constantly mutating the state.

So, let’s move onto a declarative approach with the reduce method, which gets us to a slightly cleaner solution:

const calculateTotal = () => {
  return cart.reduce((prev, next) => {
    let total = prev + next.price;
    if (next.extras) {
      total += next.extras.reduce((prev, next) => {
        return prev + next.price;
      }, 0);
    }
    return total;
  }, 0);
};

const total = calculateTotal();
console.log(total); // 647

Easier to grasp, but the main issue here is we’re introducing repeated code with lots of prev + next.price, whilst having a reduce inside reduce.

Many developers struggle to grasp Array.prototype.reduce at the best of times, let alone a nested one with some conditional checks and variable mutation.

Can we do better? We sure can. Recursion is the answer.

What does a recursive function allow us to do? Call itself to reuse the logic inside of it.

Here’s the general idea:

const doSomething = () => {
  if (condition) {
    doSomething(); // do it again
  }
  // don't do it again
};

// do it once
doSomething();

This allows us to keep the function small, predictable and reuse it where it makes sense.

The first change we’ll make is rename our cart parameter to data so we can use it for both cart and extras, since the data structures both contain a price.

We can now avoid using let and can switch to a const, preventing any internal variable mutations:

const calculateTotal = (data) => {
  return data.reduce((prev, next) => {
    if (next.extras) {
      return calculateTotal(next.extras) + prev + next.price;
    }
    return prev + next.price;
  }, 0);
};

const total = calculateTotal(cart);
console.log(total); // 647

We kick off the first function call by passing cart, which then uses reduce and captures the price of the accumulated value, starting at 0.

If it sees an extras property, it calls itself and passes in the extras array, which calculates that price again and returns it - seeing as there is no extras property on the nested data.

Once that’s complete, it uses return to pass back the final value.

And that’s it, this could also be condensed into a ternary statement, complete with destructuring and an implicit return statement:

const calculateTotal = (data) => 
  data.reduce((prev, { price, extras }) => (extras ? calculateTotal(extras) : 0) + prev + price, 0);

const total = calculateTotal(cart);
console.log(total); // 647

Simply beautiful. Enjoy recursion!

Custom Class Objects

« Constructor Functions and "new"