How to Recursively Traverse JSON Objects

I’ve found that it’s quite rare to require recursion in application code, however, every now and then I need to write a function that operates on a tree of unknown depth, like a JSON object, and it’s often best done recursively. While recursion can be rare, it’s important to at least be able to recognize when a problem is best solved recursively so we can implement a good solution when the time comes.

Before we dive too far into the tutorial, if you’re interested in a deeper understanding of recursion and other functional principles, check out the course I just launched, Intro to Functional Programming. Now let’s get back to the article.

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:

  • Easier to read and understand
  • Less memory utilization – Recursive functions keep all calls on the stack until the base case is reached
  • Faster compute time – Recursive functions come with the overhead of an entire function call for each step
  • If there is a bug in the recursion, the program is likely to enter an infinite loop

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.

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.

Likewise, even if a compiler does support loops, some problems are simpler to solve with a recursive function. A good example is tree-traversal. I often find myself writing recursive functions to find every property of an arbitrary JSON object, or looking through every file in a folder that can 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.

Thanks for reading, now take a course!

Interested in a high-paying job in tech? Land interviews and pass them with flying colors after taking my hands-on coding courses.

Questions?

Follow and hit me up on Twitter @q_vault if you have any questions or comments. If I’ve made a mistake in the article be sure to let me know so I can get it corrected!

Subscribe to my newsletter for more coding articles delivered straight to your inbox.

Related Articles

3 thoughts on “How to Recursively Traverse JSON Objects”

  1. There is no such thing as a “JSON Object” there is JSON (a UTF-8 string of an encoded value) and there are Objects (in memory representation of properties and values).

    • Well according to the JSON standards

      4. Objects

      An object structure is represented as a pair of curly brackets
      surrounding zero or more name/value pairs (or members). A name is a
      string. A single colon comes after each name, separating the name
      from the value. A single comma separates a value from a following
      name. The names within an object SHOULD be unique.

    • I agree that the vernacular is strange (JavaScript Object Notation Object), but I think its a decent way of describing the entire blob. Perhaps JSON struct? JSON blob? idk hahah

Comments are closed.

%d bloggers like this: