Recursion vs iteration of tree structure

Question

Some recursive code is part of a particularly slow path of a project. Out of curiosity I was playing around with reimplementing the code using stack context iteration instead of recursion. Below are snippets reduced to just the iteration patterns of tree elements using a DOM structure for simplicity.

I was surprised when benchmarking the code that the recursive variant was faster than iterative approaches. Is there a flaw in my implementations (they each iterate the same number of elements to the same depth)? The snippets aren't strictly equivalent in the order they touch the elements though I doubt that effects the performance.

---

Recursive depth first approach

function iterate(current, depth) {
    var children = current.childNodes;
    for (var i = 0, len = children.length; i < len; i++) {
        iterate(children[i], depth + 1);
    }
}
iterate(parentElement, 0);

Iterative breadth first forwards

var stack = [{
    depth: 0,
    element: treeHeadNode
}];
var stackItem = 0;
var current;
var children, i, len;
var depth;

while (current = stack[stackItem++]) {
    //get the arguments
    depth = current.depth;
    current = current.element;
    children = current.childNodes;
    for (i = 0, len = children.length; i < len; i++) {
        stack.push({ //pass args via object or array
            element: children[i],
            depth: depth + 1
        });
    }
}

Iterative breadth first backwards approach

var stack = [{
    depth: 0,
    element: treeHeadNode
}];
var current;
var children, i, len;
var depth;
while (current = stack.pop()) {
    //get the arguments
    depth = current.depth;
    current = current.element;
    children = current.childNodes;
    for (i = 0, len = children.length; i < len; i++) {
        stack.push({ //pass args via object or array
            element: children[i],
            depth: depth + 1
        });
    }
}

---

I was expecting the second snippet to be fastest in JS (no array popping), is there opportunity for further optimization to improve the performance of the iterative approach? I believe part of the slowness is creating the arguments in an object (i.e. {depth: depth+1,element: someElement}). The recursive snippet is more intuitive and explicit and may benefit from tail recursion in ES6 interpretors.

Repeating myself, is there a more performant way to iterate tree data structures in JavaScript than recursively?

JSPerf comparing the snippets

Answer 1

I would have completely agreed with the idea that iterative should be faster than recursive, I have seen proof to that effect many times in other languages. It is however harder to read. Here however, in JavaScript perhaps it is not, at least the benchmarks seem to suggest that the necessary object creation outweighs the function call overhead.

To that end these two examples based on yours illustrate that it is the object creation, and array manipulation that lead to the lower performance of the iterative approach. These two examples leverage the objects being iterated to create a linked list of those objects. This has the downside that it modifies each object traversed and so may not be desirable, beyond illustrating the performance difference.

Within a margin of error, these methods outperform the optimized recursive algorithm.

Breadth-First

// simulates operations for walking through tree using iteration
parentElement.depth = 0;
parentElement.next = null;

var children, i, len;
var depth;
current = parentElement;
while (current) {
  depth = current.depth;
  children = current.childNodes;
  //removes this item from the linked list
  current = current.next;
  for (i = 0, len = children.length; i < len; i++) {
    child = children[i];
    child.depth = depth+1;
    //place new item at the head of the list
    child.next = current;
    current = child;
  }
}

Depth-First

// simulates operations for walking through tree using iteration
parentElement.depth = 0;
parentElement.next = null;

var children, i, len;
var depth;
var current,last;
current = parentElement;
last = current;

while (current) {
  children = current.childNodes;
    for (i = 0, len = children.length; i < len; i++) {
      child = children[i];
      child.depth = current.depth+1;
      child.next = null;
      //place new item at the tail of the list
      last.next = child;
      last = child;
    }
  //removes this item from the linked list
  current = current.next;
}

JSPerf Comparison

Answer 2

This question is a couple of years old but it came up in Google and I don't see a satisfying answer, so here goes.

The recursive version is fast because the only overhead it has is the function call. When recursion is slower than iteration that small overhead is usually the reason. However in this case the iterative version has to do a lot of extra work as the data is in a recursive shape.

To optimize the execution of any code that depends on a recursive data structure you should look into replacing the structure or - in case that is infeasible - caching the data into an array for faster iteration. When even that is not possible recursion is likely your best bet.