Recursion vs iteration of tree structure

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 f

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

StackExchange Code Review Q#47932, answer score: 12