cost of recursion

JavaScript performance comparison

Test case created by mhevery

Preparation code


      
      <script>
Benchmark.prototype.setup = function() {
  var root = createTree(null, 15);
  
  function createTree(parent, depth) {
    if (depth > 0) {
      var obj = {
        value: 1,
        left: null,
        right: null,
        parent: null, 
        next: null,
      };
      obj.left = createTree(depth - 1);
      obj.right = createTree(depth - 1);
      obj.left && (obj.left.next = obj.right);
      return obj;
    }
    return null;
  }
  
  function recursiveSum(obj) {
    if (obj !== null) {
      return obj.value + recursiveSum(obj.left) + recursiveSum(obj.right);
    } else {
      return 0;
    }
  }
  
  var stack = [];

};
</script>

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in CCBot 2.0.0 / Other 0.0.0
Test Ops/sec
recursive
return recursiveSum(root);
pending…
non-recursive
var depth = 0;
stack[depth++] = root;
var sum = 0;
while(depth !== 0) {
  var top = stack[--depth];
  sum += top.value;
  if (top.left !== null) stack[depth++] = top.left;
  if (top.right !== null) stack[depth++] = top.right;
}
return sum;
pending…
walking
var current = null;
var next = root;
var sum = 0;
while (next !== null) {
  current = next;
  sum += current.value;
  if ((next = current.left) === null) {
    // we are out of next, so go back to parent
    next = current.parent;
  }
}
pending…

You can edit these tests or add even more tests to this page by appending /edit to the URL.

Compare results of other browsers

0 Comments