What is recursion?

#cs #computerscience #javascript

This article was originally published on mariokandut.com.

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".

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 inlcude 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 recurssion 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