This article was originally published onmariokandut.com.

Let's start with a Google easter egg for developers. Stop reading and head over togoogle.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 calledrecursion and you just used it. 😊

Recursion simply means “self reference”. And when something refers to itself or describes itself, it is called recursive. In programmingrecursion 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 asdivide-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'sN otU nix!". Find morehere.

When using recursion in a non-functional programming language, and you don't have a stop-condition, you will get an errorMaximum call stack size exceeded , when you execute your function. The error meansstack 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 theif (num === -1).

Let's break down the function execution:

countDown(3)// stop-condition falseconsole.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 fromFunFunFunctions, 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 resultconsole.log(JSON.stringify(makeTree(categories, null), null, 2))// or if you are using the console in ChromemakeTree(categories, null)

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

// First iterationmakeTree(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 anyquestions , use thecomment function orsend me a message on twitter@mariokandut.

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