6,159 reads

How to use Recursion to Traverse JSON Objects and the Filesystem

by Lane WagnerSeptember 10th, 2020

Too Long; Didn't Read

How to use Recursion to Traverse JSON Objects and the Filesystem. Recursion is a process in which a function calls itself. It is important to be able to recognize when a problem is best solved recursively. All iterative programs can be written using recursion, and all recursion programs are written using iteration. This is because it is much simpler to write an interpreter that can handle recursion than it is to write one that supports loops. The primary reason to choose recursion over iteration is simplicity.

Companies Mentioned

featured image - How to use Recursion to Traverse JSON Objects and the Filesystem

I work primarily on application-level programs, so I tend to not use recursion very often. However, every now and then I need a function that is best solved recursively. It is important to be able to recognize when a problem is best solved recursively, and to be able to write it when the time comes.

What is Recursion?

Recursion is a process in which a function calls itself.

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

So Why Use Recursion?

All iterative programs can be written using recursion, and all recursive programs can be written using iteration. This is because both systems are, unless limited by the implementation, turing complete.

mechanical turing machine

The primary reason to choose recursion over iteration is simplicity.

Many years ago many compilers and interpreters didn't support the syntax for iteration. For-loops simply didn't exist. This is because it is 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)
    }
  });
};