Explaining Recursion in JavaScript

In math, linguistics, and art, recursion refers to the occurrence of a thing defined in terms of itself. In computer science, recursion refers to a function that calls itself. Recursive functions solve complex problems through the “divide-and-conquer” method(a method to solve problems that consist of solving smaller portions of the same problem until you solve the original, larger problem.)

Recursion is no doubt one of the oldest concepts in programming. It’s the paradigm where a function calls itself. This technique is usually used to solve problems that require breaking them into smaller subproblems. In this article, we’ll discuss recursion and show examples of its application.

Two basic cases

For recursive functions to be implemented correctly, they must have two cases, so that Stack overflow is avoided and computation finishes correctly.

Base Case

The base case (also known as the terminating case) stops a function from calling itself when a given condition is reached.

For example, check out the following function, which prints numbers counting down from n to 0:

 function countDownToZero(n) {
     // base case. Stop at 0
     if(n < 0) {
         return; // stop the function
     } else {
         console.log(n);
         countDownToZero(n - 1)
     }
 }

countDownToZero(5);

output:

// 5
// 4
// 3
// 2
// 1
// 0

In the preceding code, the base case is when n is smaller than 0 because we want to stop counting at 0. If a negative number is given as the input, the countDownToZero function will not print that number because of the base case.

Recursive Case

Simply stated: Our function is calling itself. In the countDownToZero example, countDownToZero(n-1); is where the recursion actually happens.

 function countDownToZero(n) {
     .....
     // recursive case
     } else {
         console.log(n);
         countDownToZero(n - 1) // count down 1
     }
 }

countDownToZero(5);

The call stack and recursion

When a function calls itself recursively, it gets added to the call stack. Stacks are LIFO (Last In, First Out) structures, meaning that the last item added to the stack is the first one to be removed from the stack later.

Let’s see how the Stack handles our countDownToZero recursive function:

 function countDownToZero(n) {
     // base case. Stop at 0
     if(n < 0) {
         return; // stop the function
     } else {
         console.log(n);
         countDownToZero(n - 1)
     }
 }

countDownToZero(5);

This is why a base case is critical: without a base case, an infinite loop will cause a stack overflow.

Applying Recursion

In programming, all problems that can be solved with a recursive approach also have an iterative approach that can be used to solve them. That being said, for many problems recursion provides a much easier solution. An example is working with tree structures, such as deeply nested objects.

Reading a deeply nested field

Let’s assume we have an object like the following, and we want to access a deeply nested field within the object:

 const person = {
     data: {
         age: 20,
         name: {first_name: "John", last_name: "Doe"},
     }
 }
 
 console.log(person.data.last_name)

Output:

undefined

We want to read the last_name of person. We have to write person.data.last_name. And, of course, if some data is missing, we will get undefined.

To solve this problem, we use helpers like lodash’s get method.

get(person, 'data.name.last_name', 'unknown');

This utility safely tries to read the value and returns the 'unknown' string if it doesn’t exist.

Here is what the implementation of such a utility may look like using a recursive function:

 function get(obj, path, fallback) {
     const parts = path.split(".");
     const key = parts.shift();
     if(typeof obj[key] !== "undefined") {
         return parts.length > 0 ? get(obj[key], parts.join("."), fallback) : obj[key];
     }
     return fallback;
 }

console.log(get(person, "data.name.first_name"));
console.log(get(person, "data.name.last_name"));
console.log(get(person, "data.age"));
console.log(get(person, "data.date_of_birth"));
console.log(get(person, "data.date_of_birth", false));

Output:

John 
Doe
30
undefined
false

Notice how get calls itself recursively until it reaches the path’s last part. Also, the fallback parameter is returned when we try to read a value that doesn’t exist—console.log(get(person, "data.date_of_birth")) returns undefined which is the default value when a fallback is not provided. When a fallback is provided, the provided value is returned—console.log(get(person, "data.date_of_birth", false)); returns false.

Doing a deep copy of an object

As per MDN:

A deep copy of an object is a copy whose properties do not share the same references (point to the same underlying values) as those of the source object from which the copy was made. As a result, when you change either the source or the copy, you can be assured you’re not causing the other object to change too; that is, you won’t unintentionally be causing changes to the source or copy that you don’t expect. That behavior contrasts with the behavior of a shallow copy, in which changes to the source or the copy cause the other object to change (because the two objects share the same references).

Let’s see how to create a deep copy of an object using recursion.

const createDeepCopy = (input) => {
  if (typeof input !== "object" || input === null) {
    return input; //BASE CASE
  }
    
  let copy = Array.isArray(input) ? [] : {};
    
  for (let key in input) {
    const value = input[key];
    copy[key] = createDeepCopy(value); //recursive call for each element of 
};

In the preceding code createDeepCopy() is a recursive function. It creates a deep copy of an object passed to it through its input argument.

Base Case

if (typeof input !== "object" || input === null) {
    return input; //BASE CASE
  }

In the preceding code, if the input is a primitive type(string, number, etc.) or equal to a null value it is returned, this ensures only objects that are not null are passed in as input.

Recursive Case

let copy = Array.isArray(input) ? [] : {};
    
  for (let key in input) {
    const value = input[key];
    copy[key] = createDeepCopy(value); //recursive call for each element of an array/object
  }

  return copy;

For the recursive case:

• The copy of the object is stored in the let copy; variable.
• Then we check if the object is an array or an object let copy = Array.isArray(input) ? [] : {};, if true, a copy of an empty array is initialized; else, a copy of an empty object is initialized.
• Then loop through the object’s keys(object) or indexes(array) using a for in loop.
• The corresponding key or index value is stored in the value variable—const value = input[key];.
• The createDeepCopy(value) function is called recursively with value.
• The result is stored with the same key name in our copy object—copy[key] = createDeepCopy(value).
• Our object copy is returned—return copy;.

We are essentially recursively calling the createDeepCopy() function for each element in our reference object(the object we are copying from). If the data type of the element is primitive, it will be returned as it is; else, createDeepCopy() will be called recursive until it reaches the base case.

For example, let’s pass an object into the createDeepCopy() function to get its deep copy equivalent.

let originalCopy = [
  undefined,
  null,
  "Hello",
  20,
  {
      location: {
          city: "new york",
        },
  },
];

let deepCopied = createDeepCopy(originalCopy);

deepCopied[2] = "Bonjour"
deepCopied[3] = 30
deepCopied[4].location.city = "lagos"


console.log(deepCopied, originalCopy);

Output:

/// New Copy
[ undefined, null, 'Bonjour', 30, {location: { city: 'lagos' } } ]

/// Original Copy
[ undefined, null, 'Hello', 20, {location: { city: 'new york' } } ]

In the preceding code, we can verify that the object passed into createDeepCopy() is actually copied. From the output, the values changed in the deepCopied object are not reflected in the object they are copied from(originalCopy). View the Demo Here

Conclusion

With the basic understanding of recursion, it can now be used as part of your problem-solving arsenal as a developer—especially for problems that require breaking them into smaller subproblems.

A TIP FROM THE EDITOR: Don’t miss our Forever Functional: Solving Puzzles With Recursion And JavaScript article, with several more examples of recursion application.

Gain Debugging Superpowers

Unleash the power of session replay to reproduce bugs and track user frustrations. Get complete visibility into your frontend with OpenReplay, the most advanced open-source session replay tool for developers.

Check our GitHub Repo