What is recursion?
© https://unsplash.com/@barnabartis

What is recursion?

Divide and Conquer - simply explained without Fibonacci.

ByMario Kandut

honey pot logo

Europe’s developer-focused job platform

Let companies apply to you

Developer-focused, salary and tech stack upfront.

Just one profile, no job applications!

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". google-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;
  countDown(num - 1);


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:

// stop-condition false
countDown(3 - 1);
// stop-condition false
countDown(2 - 1);
// stop-condition false
countDown(1 - 1);
// stop-condition false
// stop-condition true

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

Scroll to top ↑