What is recursion?

Let's start with a Google easter egg for developers. Stop reading and head over to google.com and search for 'recursion'. What do you see?

The result should look like this. Click on the suggestion "Did you mean: recursion".

💰 The Pragmatic Programmer: journey to mastery. 💰 One of the best books in software development, sold over 200,000 times.

As you just have experienced, the page reloads and you see the same results. So it called itself, this is basically called recursion and you just used it. 😊

Recursion simply means “self reference”. And when something refers to itself or describes itself, it is called recursive. In programming recursion is when a function calls itself until a 'base condition' is true.

Think of it as a way of solving a problem. You break down a problem into a smaller problem until it's small enough that it can be easily solved and then combine them again. This pattern is very common in computer science and often referred to as divide-and-conquer.

A common computer programming tactic is to divide a problem into sub-problems of the same type as the original, solve those sub-problems, and combine the results. This is often referred to as the divide-and-conquer method; wikipedia

In computer science, recursive acronyms are also widely used. For example: GNU is a recursive acronym. "G NU's N ot U nix!". Find more here.

When using recursion in a non-functional programming language, and you don't have a stop-condition, you will get an error Maximum call stack size exceeded, when you execute your function. The error means stack overflow or no space in memory for your function. So always include a stop-condition.

Let's write a countdown function. It should take an integer as an argument and log the countdown in the console.

let countDown = num => {
  if (num === -1) return;
  console.log(num);
  countDown(num - 1);
};

countDown(3);

This function will print the numbers 3 2 1 0 in the console. The stop-condition is the if (num === -1).

Let's break down the function execution:

countDown(3);
// stop-condition false
console.log(3);
countDown(3 - 1);
// stop-condition false
console.log(2);
countDown(2 - 1);
// stop-condition false
console.log(1);
countDown(1 - 1);
// stop-condition false
console.log(0);
countDown(0);
// stop-condition true
return;

Yes, I know what you are thinking, you could easily use a loop for this. And yes, you are right, you could. You can replace also a loop with a recursive function, also vice-versa, but not always.

The concept of recursion may not seem like much, but recursion allows us to write more elegant solutions than deeply nested for loops.

Another basic example for recursion would be this: A recursive function that returns the sum of array elements until n-elements. It would take an array and an integer as arguments.

function sumUntil(arr, n) {
  if (n <= 0) {
    return arr[0];
  }
  return sumUntil(arr, n - 1) + arr[n];
}

The recursive function sumUntil breaks down like this. In the base case, where n <= 0, it returns the result (arr[0]). For larger values of n, it calls itself, but with n - 1. That function call is evaluated in the same way, calling sumUntil again until n = 0. At this point, all the functions can return and the original sumUntil returns the answer.

I know, you could have done this easily with array methods, like .splice and .reduce combined, maybe even lodash has a method for this. In programming there are many ways which lead to the same result, although performance matters in some cases.

A more versatile example is when you want to create a deeply nested object from nested data in a relational database. This example is from FunFunFunctions, check it out.

This is the category array you get from the database export.

let categories = [
  { id: 'animals', parent: null },
  { id: 'mammals', parent: 'animals' },
  { id: 'cats', parent: 'mammals' },
  { id: 'dogs', parent: 'mammals' },
  { id: 'persian', parent: 'cats' },
  { id: 'siamese', parent: 'cats' },
  { id: 'chihuahua', parent: 'dogs' },
  { id: 'labrador', parent: 'dogs' },
];

The output should look like this:

{
  animals : {
    mammals: {
      cats: {
        persian: null,
        siamese: null,
      },
      dogs: {
        chihuahua: null,
        labrador: null,
      },
    }
  }
}

Recursive Function to the rescue:

let makeTree = (categories, parent) => {
  let node = {};
  categories
    .filter(cat => cat.parent === parent)
    .forEach(cat => (node[cat.id] = makeTree(categories, cat.id)));
  console.log(node);
  return node;
};

// To call the function log the result
console.log(JSON.stringify(makeTree(categories, null), null, 2));

// or if you are using the console in Chrome
makeTree(categories, null);

What is happening here? Let's break down the function execution.

// First iteration
makeTree(categories, null);
categories
  .filter(cat => cat.parent === null)
  // One item with parent "null" left. id: animals
  .forEach(
    cat => (node['animals'] = makeTree(categories, 'animals')),
  );
// second iteration
categories
  .filter(cat => cat.parent === 'animals')
  // One item with parent 'animals' left. => id: mammals
  .forEach(
    cat => (node['mammals'] = makeTree(categories, 'mammals')),
  );
// third iteration
categories
  .filter(cat => cat.parent === 'mammals')
  // Two items with parent 'mammals' left.
  // { id: 'cats', parent: 'mammals' },
  // { id: 'dogs', parent: 'mammals' },
  .forEach(
    cat =>
      // node[cat.id] = makeTree(categories, cat.id))
      // Once for CATS
      // Once for DOGS
      (node['cats'] = makeTree(categories, 'cats')),
  );
// fourth iteration for CATS
categories
  .filter(cat => cat.parent === 'cats')
  // Two items with parent 'cats' left.
  // { id: 'persian', parent: 'cats' },
  // { id: 'siamese', parent: 'cats' },
  .forEach(
    cat =>
      // node[cat.id] = makeTree(categories, cat.id))
      // Once for 'persian'
      // Once for 'siamese'
      (node['siamese'] = makeTree(categories, 'siamese')),
    // .... and so on
  );

If you look at the code and you are searching for the stop condition, then look at the filter method. The execution is stopped if all elements in the categories array are filtered out.

🥁, that is recursion. Just a function, which calls itself, until it doesn't. Checkout the references for more information.

I hope I could explain recursion to you 🤔, if you have any questions, use the comment function or send me a message on twitter @mariokandut.

References (and Big thanks): Hackerrank, FunFunFunctions, wikipedia, Javascript, StackExchange, MIT, FreeCodeCamp