From Jimbojw.com

In last week's Weekly Web Hack, I showed how to make recursive anonymous JavaScript functions. This week, I'll demonstrate how to unroll a recursive DOM traversal function into a potentially less expensive, non-recursive form.

DOM traversal recursion

One common reason to use-case for recursive JavaScript functions is DOM tree traversal. For example, consider the method Element.collectTextNodes from Scriptaculous's effects.js library. This method traverses all of a DOM node's descendents and collects the contents of text nodes into a single concatenated string.

The source for this method (as of Scriptaculous version 1.8.0) appears here:

Element.collectTextNodes = function(element) {  
  return $A($(element).childNodes).collect( function(node) {
    return (node.nodeType==3 ? node.nodeValue : 
      (node.hasChildNodes() ? Element.collectTextNodes(node) : ''));
  }).flatten().join('');
};

Despite looking a little complex, the code is actually pretty straightforward. It does the following:

1. Gets a collection of the element's child nodes and casts it to an Array
2. Loops over each element, recursively building a tree of strings and arrays
3. Merges the tree into a flat array containing just strings and returns their concatenation.

Unrolled traversal

Now, here is an alternative implementation, which does not use recursion:

Element.collectTextNodes = function(element) {
  var toscan = $A($(element).childNodes), results = [];
  for (var i=0; i<toscan.length; i++) {
    var node = toscan[i];
    if (node.nodeType==3) { results.push(node.nodeValue); continue; }
    toscan.splice(i, 1);
    var j = i--;
    $A($(node).childNodes).map( function(item) { 
      toscan.splice(j++, 0, item);
    } );
  }
  return results.join('');
};

Unlike the first example, this one is a bit longer and abstains from a good deal of the Prototype/Scriptaculous "magic" featured in the former.

Nevertheless, it's also fairly easy to understand - it does the following:

1. Initializes an array called toscan which contains all the elements child nodes
2. Loops over the items in toscan, adding text nodes to the results array
3. When a non-text node is encountered, it is replaced (spliced) in the toscan array by its own children, and the incrementor is decremented (i--).
4. Finally, when all the nodes have been scanned, the concatenation of the results array is returned

You'll notice that this second example breaks one of the ivory rules of looping - only alter the loop variable in one place, and only in one direction. Of course, the trade-off here is that by abusing this tenant, we get to abandon recursion.

Whether or not this will have any real impact on performance is to be seen. It may not make a difference, and the non-recursive call may even be slower in practice. In either case, I hope these examples are instructive.

Recursion is an important concept to understand in software development, but it can become an expensive crutch if used improperly. After all, the curve is a circle.

Enjoy! As always I'll be happy to answer any questions.

---

Got something to say?

Leave a comment

Sorry, comments are disabled.

or, read what others have said...