Thomas McDevitt

javascript: practical examples of recursion

As mentioned in my previous post, a recursive function in programming is one that repeatedly calls itself — usually until a termination condition is met. Whilst most examples of recursive functions do something mathematical, there are other applications that are more likely to be useful for JavaScript developers.

Recursion is typically useful when exploring ‘tree’ type structures where the exact layout will not always be known; two examples of this are given below.

walking the dom

As far as tree structures go, the DOM is one of the most important we’ll have to handle with JavaScript. Just as an example, I’ll traverse the DOM to find all of the list items and add a new class to them.

function crawlDom(node) {
  if (node.tagName === 'LI') {
    node.classList.add('list-item-new-class');
  }

  node.childNodes.forEach(function(nestedNode) {
    crawlDom(nestedNode);
  });

  // no return value is needed
}

crawlDom(document.body); // off it goes

The function obviously starts from a given parent node. Here, it’s just document.body but it could be any node on the page as returned by document.querySelector or similar. If the node is a list item, it adds our new class to it. Whether or not it’s a list item, the function loops through all of its children and reruns the check. This kind of function is useful to inspect the DOM programmatically.

json crawlers

The above approach works for exploring XML and JSON as well as HTML. I’ve recently been working with data comparison and I’ve thus used recursion to ‘pivot’ JSON objects into different formats to make the data easier to analyse. Here’s a shortened version of the solution I came up with.

var crawlObj = function(obj, key) {

  var values = [];

  if (!_.isObject(obj)) {
    // if this is a primitive value
    values = obj;
  } else {
    for (var property in obj) {
      // loop through object properties or array indices
      values.push(crawlObj(obj[property], property));
    }
  }
  
  if (!key) {
    // original object
    return values;
  }

  return {
    key: key,
    values: values,
    type: (typeof obj)
  }
    
}

This can run against any object and give back a hierarchical array that reports all of the object’s properties and details about how they’re nested. Whilst it won’t be useful for manual inspection of larger objects, once again, it’s great for automated analysis of data — in my case, I would pivot two objects using this function and then compare the data from both using the return value. Here’s an example output of the above function.

var person = {
name: 'Bradley',
hair: {
  color: 'blonde',
  length: 'short'
};

crawlObj(person);

// returns...
[
  {
    "key": "name",
    "values": "Bradley",
    "type": "string"
  },
  {
    "key": "hair",
    "values": [
      {
        "key": "color",
        "values": "blonde",
        "type": "string"
      },
      {
        "key": "length",
        "values": "short",
        "type": "string"
      }
    ],
    "type": "object"
  }
]

have you got any other use cases?

Hopefully, this post demonstrates some of the ways recursion can be useful in JavaScript. If you have any other interesting use cases, comments on the above or if the examples given here have been at all useful to you, get in touch on Twitter or leave us a comment below. Happy scripting! 🙂

If you enjoyed the read, drop us a comment below or share the article, follow us on Twitter or subscribe to our #MetaBeers newsletter. Before you go, grab a PDF of the article, and let us know if it’s time we worked together.

blog comments powered by Disqus