Recursion is often a topic that strikes fear into beginner programmers. It’s a useful technique though and doesn’t have to be scary!

In this article, we’re going to take a look at what recursion is and how it works. We’ll also go through some examples of when it’s useful and leave you with some challenges to have a go at yourself.

What is recursion? 🤔

Recursion is a programming technique that involves using functions that call themselves repeatedly until certain conditions are met. Once the conditions are met, a recursive function will return a result.

Recursion is a powerful technique and is often used in functional programming, in fact, some purely functional languages such as Elm and Haskell don’t have any concept of loops and completely rely on recursion instead 😲. It can help to make you a better programmer and keep your code succinct and tidy.

Your first recursive function

For our first recursive function we’re going to stick to the classic factorial function. The factorial function will find the product of every number from 1 up to that number by multiplying them all together. For example factorial(4) should return 24 because

This is how you could implement a factorial function using a traditional for loop:

const factorialIteration = n => {
  if(n === 0) return 1
  let result = 1;
  for(let i =n;i > 0; i--){
    result = result * i
  }
  return result
}

Here is how the factorial function would look like written as a recursive function:

const factorialRecursive = n => {
  if(n === 0) return 1
  return n * factorialRecursive(n - 1)
}

Notice  how much shorter the recursive function is. It can be made even shorter and more elegant by using a ternary operator:

const factorialRecursive = n => 
  n === 0 ? 1 
: n * factorialRecursive(n - 1)

All recursive functions contain two key elements:

  1. A base case that returns a value if a condition is met.
  2. A recursive step that returns a call to the function again. Be careful with this step though, it has to call itself with different arguments, otherwise you’ll end up stuck in an infinite loop!

In our factorialRecursive example above, the base case is on the first line: when the argument is 0, the function will return a value of 1.

The recursive step is on the second line and returns n multiplied by the return value of factorialRecursive but using an argument of n - 1 instead of n.

If you give this a try, you’ll see it returns the following results:

factorialRecursive(0)
<< 1

This is the base case and simply returns 1 because the argument, n was 0.

factorialRecursive(1)
<< 1

This function call will apply the recursive step and return 1 multiplied by the value of factorialRecursive(0) which we just saw was 1. So this function will return 1 * 1 which is of course 1.

Things get a bit more interesting when we use an argument of 2:

factorialRecursive(2)
<< 2

This function applies the recursive step and returns 2 multiplied by recursiveFactorial(1). This returns 1 multiplied by recursiveFactorial(0). recursiveFactorial(0) hits the base case and returns 1. We can then backtrack and find that recursiveFactorial(1) is 1 * 1 which means that recursiveFactorial(2) is 2 * 1.

Last of all Let’s look at how recursiveFactorial(4) works:

  • recursiveFactorial(4) returns 4 * recursiveFactorial(3)
  • recursiveFactorial(3) returns 3 * recursiveFactorial(2
  • recursiveFactorial(2) returns 2 * recursiveFactorial(1
  • recursiveFactorial(1) returns 1 * recursiveFactorial(0)
  • recursiveFactorial(0) returns 1

And now backtracking:

  • recursiveFactorial(1) returns 1 * 1 = 1
  • recursiveFactorial(2) returns 2 * 1 = 2
  • recursiveFactorial(3) returns 3 * 2 = 6
  • recursiveFactorial(4) returns 4 * 6 = 24

How is recursion helpful?

Recursion is particularly helpful for solving problems that can be broken down into smaller parts or have an obvious recursive structure, such as traversing a network or searching a data structure such as an object or array. Some mathematical operations (like the factorial example above) are particularly suited to using recursion.

Recursive functions are often shorter and more elegant than using loops and can often solve a problem in a much better way. Once you get used to how they work, they can often be easier to follow the logic of them. And shorter functions are always easier to debug.

Some recursion examples

Now we’ve covered what recursive functions are and why they’re useful, let’s take a look at some practical examples.

Reverse an array

The following function will accept an array and return the array in reverse:

const reverse = ([head, ...tail]) => 
  tail.length ? [...reverse(tail), head] 
  : [head]

The first thing to note about this function is the parameter list destructures the array into head and tail. The head represents the first value in the array and tail represents the rest of the values in the array. This is a very common pattern when writing recursion using arrays.

The base case for this function is if the tail array is empty then we just return an array containing the value of head. This basically means that if we provide an argument of an array with a single value then it will just return the same array, since an array of just one value written in reverse won’t actually change.

The recursive step to this function is to place the value of head after the return value of reverse(tail).

This means that if I call reverse([1,2,3]), the following stack trace will occur:

  • reverse([1,2,3]) returns [...reverse[2,3],1]
  • reverse([2,3]) returns [...reverse[3],2]
  • reverse([3]) returns [3]

And now backtracking:

  • reverse([2,3]) returns [3,2]
  • reverse([1,2,3]) returns [3,2,1]

Remove vowels from a string

The following function will remove vowels from a string:

const removeVowels = str => 
  str.length ? 
  ["A","E","I","O","U"].includes(str.toUpperCase()[0]) ? removeVowels(str.slice(1)) 
  : str[0] + removeVowels(str.slice(1)) 
  : ""

The base case here is a test to see if the string has any length, if it doesn’t then we just return an empty string.

The recursive step tests to see if the first character, str[0] is a vowel, by using the includes method of an array containing all the vowels. If it is a vowel, then we recursively call the removeVowels function passing str.slice(1) as a parameter if the character is a vowel which will remove the first character from the string. If the character is not a vowel then we will return the character + a recursive call with str.slice(1) passed as an argument.

Let’s have a look at how the call stack will look when we call removeVowels("hey"):

  • removeVowels("hey") returns "h" + returnVowels("ey")
  • removeVowels("ey") returns returnVowels("y")
  • removeVowels("y") returns "y" + returnVowels("")
  • removeVowels("") returns ""

Backtracking now gives us the following:

  • removeVowels("y") returns "y" + "", which is just the string "y"
  • removeVowels("ey") returns "y"
  • removeVowels("hey") returns "h" + "y" which is just the string "hy"

Quick sort

The quicksort algorithm is a classic algorithm from the world of Computer Science. It can be implemented as a recursive function that can sort an array of values using the following code:

const quicksort = ([head,...tail]) => 
 head === undefined ? []
 : [ ...quicksort(tail.filter(n => n <= head)),
     head,
     ...quicksort(tail.filter(n => n > head))]

It works by taking the first item in the array, the head and placing all the values smaller than head before it and all the values larger than head after it in a new array. It then calls the function recursively on the values above and below head. The base case is if head is undefined, which means the array is empty, this returns an empty array. One interesting thing to note is that each recursive step makes two calls to the quicksort function, meaning that the number of function calls doubles with every step, which will cause the stack to build up exponentially.

Let’s see how this would work with the array [3,6,7,2,5]:

  • quicksort([3,6,7,2,5]) returns [...quicksort([2]),3,...quicksort([6,7,5])]
  • quicksort([2]) returns [...quicksort([]),2,...quicksort([])] … which returns [2]
  • quicksort([6,7,5]) returns [...quicksort([5]),6,...quicksort([7])]
  • quicksort([5]) returns [...quicksort([]),5,...quicksort([])] … which returns [5]
  • quicksort([7]) returns [...quicksort([]),7,...quicksort([])] … which returns [7]

Backtracking gives:

  • quicksort([6,7,5]) returns [5,6,7]
  • quicksort([3,6,7,2,5]) returns [2,3,5,6,7]

Search an object

Recursive functions can be really useful for searching through nested object structures. For example, the following function will search an object for a particular property:

const searchObject = (obj,prop) => {
  for(let key in obj){
	  if(key === prop) return obj[key]
	  if(typeof obj[key] === "object") return searchObj(obj[key])
  }
  return "Property does not exist"
}

If a property is also an object then it will recursively call the function again on that object, as can be seen in the example below:

const company = { 
	boss: "Alice", 
	finance: { accounts: "Bob", payments: "Charlotte" },
	dev: {coders: {js: "Dave", react: "Emily"}, design: "Frank"}
}
searchObject(company,"boss")
<< "Alice"
searchObject(company,"accounts")
<< "Bob"
searchObject(company,"js")
<< "Dave"

Since company is a nested object with a varying structure (some properties have objects as properties and others don’t), a recursive function is perfect for searching the whole object until it finds the relevant property. It starts by checking if the property exists on the top level. If a property is an object then it call itself again on that property. This will continue to happen until the property is found and then its value will be returned. Otherwise the property doesn’t exist in the object, so we return a message to say this.

When to not use recursion

Recursion can often not be as efficient as using iteration in terms of performance, especially when using JavaScript which is not optimized for recursion in the same way that some functional languages are.

Recursive functions can also be difficult to debug as you have to trace back through multiple function calls. There is also the risk of creating a stack overflow when too many function calls are added to the stack. This is where the name of the Stack Overflow website came from by the way!

One way of avoiding stack overflow is to use a technique called tail call optimization… this is baked in to many functional languages, but not fully supported in JavaScript (at the time of writing, only the Safari JavaScript engine supports it). This means that  it is very important to make sure your code is fully tested in all JavaScript engines to make sure your code is performant and doesn’t result in a stack overflow.

The maximum recursion depth varies by platform but is around 100,00 when this value is exceeded, a RangeError: Maximum call stack size exceeded error will be thrown.

Tail call optimization

This is a technique that can be used to reduce the chance of stack overflow. As each new function is called, the information is passed to the next function as a parameter. This means there is no need to backtrack through all the previous functions once the base case is reached, which means that all the previous function don’t have to be kept alive in the stack. Here is an example of how to manually implement tail call optimization in the factorial function:

const factorialTailOptimized = (n,result = 1) => {
	if(n === 0) return result
	return factorialRecursive(n - 1, result * n)
}

The difference here is that the result of multiplying by each number is passed to the next call using the second parameter result. This means that each function call does not need to refer back to previous function calls to calculate the next value of result and once the base case is reached, the value of result can be returned without having to backtrack over previous functions. The process of calling the function with n = 4 can be seen in the diagram below:

factorialTailOptimized(4,1) → factorialTailOptimized(3,4) → factorialTailOptimized(2,12) → factorialTailOptimized(1,24) → factorialTailOptimized(0,24) → 24

As you can see, the final answer is building up as the second argument with each recursive function call, meaning backtracking is not needed.

Practice recursion

Now that you’ve seen how to implement recursion in JavaScript, it’s time to have a go at writing some recursive functions yourself! Here are four challenges for you to try

  1. Write a recursive function that has a single parameter n and returns the sum of the numbers from 1 - n (hint this is very similar to the factorial function we started this article off with)
  2. Write a recursive function that accepts an array as its argument and returns the largest value in the array (hint, this works in a similar way to the reverse example above, using the head and ...tail destructured arguments).
  3. Write a recursive function that accepts a number and returns the sum of its digits
  4. Write a recursive function that accepts a DOM node as its argument and adds a class of scrimba to the element and all of its child nodes.

The verdict

Well that was a quick introduction to recursive functions. They can seem a bit daunting at first, but once you’ve mastered them, they will be a useful addition to your programming skillset. The key points to remember are that a recursive function needs a base case to make sure it doesn’t result in an infinite call stack and the recursive step needs to call the function again, but with different parameters.