# 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);


var stack = [{
depth: 0,
}];
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
});
}
}


var stack = [{
depth: 0,
}];
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

-
Have you tried profiling the routines, perhaps with Google Chrome's developer tools or something like that? That should tell you where most of the time is being spent. –  Tom Barron Apr 23 at 0:13
One thing the v8 developers mentioned as a particular performance pain point was altering the "shape" of an object by adding/removing properties. They found it much faster to set a property to null which simply changes the property's value than delete it which removes it from the object entirely, altering its shape. The object the property references is garbage collected either way, so there's no memory penalty. –  David Harkness Apr 23 at 3:29
What is depth for? I see no use of it, besides adding up while it runs through the tree. –  Joseph the Dreamer Apr 23 at 10:42
@JosephtheDreamer its just a random variable there to make the solution more useful than passing only one state variable to the next operation. Haven't profiled the operations in much depth, only checked memory, thanks for the suggestion –  megawac Apr 23 at 10:49
Perhaps the recursive version performance is due to compiler tail recursion optimization? taylodl.wordpress.com/2013/06/07/… –  Brandon Oct 10 at 11:45

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.

// 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

-
You have a couple global variables (current) in the jsperf which may be hurting the performance a tad. I'm not sure creating a sll on top of the nodes is fair for the users as they may not be expecting the next property on their tree objects. –  megawac Apr 23 at 2:44
Globals were as in the original jsperf. I noted the modification of the elements as the problem with this approach and suggested it only for demonstration purposes, as I do not think you can beat the performance of the recursive approach otherwise. The function stacks are far to optimized to be beat by an array used as a stack with new objects being created on it. –  AaronM Apr 23 at 3:04
Ya, probably true - I'm actually amazed your iterative approach doesn't beat recursion (even in ie8!). –  megawac Apr 23 at 3:29
The results might vary depending on actual code, for instance, the recursive example here has very few local variables which reduces the function stack overhead. A function that was actually processing each node might have significantly more overhead. This overhead might be enough to change performance characteristics between the two implementations. Further, the recursive approach will likely use a greater amount of memory, as recursion depth increases, and as those local vars cannot be reused by each iteration. –  AaronM Apr 23 at 3:33