Prepare for a backend job by mastering computer science fundamentals

How to Recursively Traverse JSON Objects

By Lane Wagner on Sep 22, 2019

I’ve found that it’s pretty rare that I need recursion in application code, but every once in a while I need to write a function that operates on a tree of unknown depth, such as a JSON object, and that’s often best solved recursively. Even though recursion is rare, it is important to recognize when a problem is best solved recursively so that we can implement a good solution when the time comes.

What is Recursion?

Function recursion is a process in computer science that occurs when a function calls itself.

man answering two phones

For example:

function printArrayRecursive(arr, i) {
  // base case, stop recurring
  if (i === arr.length){
    return;
  }
  console.log(arr[i])
  // call ourself with the next index
  recursive(arr, i+1)
}

In the code above, printArrayRecursive prints one element from the list, then calls itself again with the next index. Each successive call to itself prints the next element, and so on. The recursion continues until the base case is reached. In our example, the base case is when the index is equal to the array’s length.

The same function looks quite a bit different in the iterative world, which you are probably more familiar with:

function printArrayIterative(arr){
  for (let i = 0; i < arr.length; i++){
    console.log(arr[i])
  }
}

In the case of simply printing the items of a list, the iterative approach is better for a number of reasons:

A simple path to your career in backend development

The pace of Boot.dev's JavaScript, Python and Go courses has been perfect for me. The diverse community in Discord is a blast, and other members are quick to help out with detailed answers and explanations.

- Daniel Gerep from Cassia, Brasil

Why Use Recursion?

Iterative programs can be written using recursion, and all recursive programs can be written using iteration. Both systems are, unless limited by the implementation, Turing complete.

mechanical turing machine

mechanical turing machine

The primary reason to choose recursion over iteration is simplicity.

Many years ago the majority of compilers and interpreters didn’t support the syntax for iteration. For-loops simply didn’t exist. This is primarily because it’s much simpler to write an interpreter that can handle recursion than it is to write one that supports loops.

Even if a compiler supports loops, some problems are easier to solve with a recursive function. A good example is tree traversal. I often write recursive functions to find every property of any JSON object, or to search every file in a folder that may have an infinite number of nested subfolders.

Examples

Recursively print all properties of a JSON object:

function printAllVals(obj) {
  for (let k in obj) {
    if (typeof obj[k] === "object") {
      printAllVals(obj[k])
    } else {
      // base case, stop recurring
      console.log(obj[k]);
    }
  }
}

Recursively print all the filenames of a folder, and its subfolders, and their subfolders, ad infinitum.

function printSubFiles(dir) {
  files = fs.readdirSync(dir);
  files.forEach(function (file) {
    absName = `${dir}/${file}`
    if (fs.statSync(absName).isDirectory()) {
      printSubFiles(absName)
    } else {
      // base case, stop recurring
      console.log(file)
    }
  });
};

When trying to figure out how to write a function recursively, think:

What is my base case? What should stop the recursion from continuing?

Once that’s hammered out, the rest of the function just needs to answer the questions,

What do I want to do with my current value?

and

How do I call myself to get to the next value?

Recursion is an important principle to understand for any programmer, and I hope this helps you be just a little better! If you’re interested in learning more about recursion and functional programming principles, take a look at our functional programming course.

Become a backend engineer by building real projects

Related Reading