Explaining Recursion In Javascript

This article was first published on the Open Replay Blog

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.

INTRODUCTION

In this article you learned the following:

• What the concept of recursion is in programming
• The 2 rules of recursion
• How to use a recursive function to get value from a deeply nested object
• How to create a deep copy of an object recursively.

TABLE OF CONTENT

• WHAT IS RECURSION

• RULES FOR RECURSION

  • Base Case
  • Recursive Case

• CALLSTACK AND RECURSION

• APPLYING RECURSION

  • Reading a deeply nested object

• CONCLUSION

  • Summary

   

WHAT IS RECURSION

“To understand recursion, one must first understand recursion.” —Stephen Hawking

  In math, linguistics, and art, recursion refers to the occurrence of a thing defined in the 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.)

   

RULES FOR RECURSION

For recursive functions to be implemented correctly, they must follow specific rules so that Stack overflow is avoided.

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 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 CALLSTACK 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 that was added to the top of the stack is the first one to be removed from the stack later on.

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 the reason why a base case is important, without a base case an infinite loop occurs which will cause stack overflow.

   

APPLYING RECURSION

In Javascript most problems that can be solved with a recursive approach, also have an iterative approach that can be used to solve them. That being said, recursion easily solves problems when working with tree structures. A deeply nested object is a tree structure.

READING A DEEPLY NESTED OBJECT FIELD

 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, if it doesn't exist returns the 'unknown' string.

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 till it reaches the last part of the path. 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.

COPYING AN OBJECT (DEEP COPY)

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 either the source or the copy may also cause the other object to change too (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 an array/object
  }

  return copy;
};

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 it evaluates to 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.
• Then 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 calling the createDeepCopy() function for each element in our reference object(the object we are copying from) recursively. If the data type of the element is a primitive data type it will be returned as it is else createDeepCopy() will be called recursive until it reaches the base case.

For example: Let's pass in 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 deepcCpied object are not reflected in the object they are copied from(originalCopy). View the Demo Here

   

CONCLUSION

With the basic understanding of recursion you now have, 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.

Summary

In this article you learned the following:

• What the concept of recursion is in programming
• The 2 rules of recursion
• How to use a recursive function to get value from a deeply nested object
• How to create a deep copy of an object recursively.