Info

Testing out how slow recursion actually is.

Preparation code

<script>
  var index = 20;
  var r5 = Math.sqrt(5);
  var phi = (1 + r5) / 2;
  
  function fibonacci_recursive(n) {
    if (n < 2) return n;
    return fibonacci_recursive(n - 2) + fibonacci_recursive(n - 1);
  }
  
  function fibonacci_loop(n) {
    if (n < 2) return n;
    var previous = 0;
    var current = 1;
    var next;
    for (var i = 1; i < n; i++) {
      next = previous + current;
      previous = current;
      current = next;
    }
    return current;
  }
  
  function fibonacci_direct(n) {
    if (n < 2) return n;
    return (Math.pow((1 + r5) / 2, n) - Math.pow((1 - r5) / 2, n)) / r5;
  }
  
  function fibonacci_direct2(n) {
    if (n < 2) return n;
    var r5 = Math.sqrt(5);
    var phi = (1 + r5) / 2;
    return (Math.pow((1 + r5) / 2, n) - Math.pow((1 - r5) / 2, n)) / r5;
  }
  
  function fibonacci_round(n) {
    if (n < 2) return n;
    return Math.round(Math.pow(phi, n) / r5);
  }
  
  function fibonacci_round2(n) {
    if (n < 2) return n;
    var r5 = Math.sqrt(5);
    var phi = (1 + r5) / 2;
    return Math.round(Math.pow(phi, n) / r5);
  }
  
  function fibonacci_recursive_memoization(n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacci_recursive_memoization(n - 1) + fibonacci_recursive_memoization(n - 2);
  }
  
  function memo(f) {
    var cache = {}
    return function(x) {
      if (typeof cache[x] === 'undefined') {
        cache[x] = f(x);
      }
      return cache[x];
    }
  }
  fibonacci_recursive_memoization = memo(fibonacci_recursive_memoization);
  
  var Y = function(F) {
      return (function(x) {
        return F(function(y) {
          return (x(x))(y);
        });
      })(function(x) {
        return F(function(y) {
          return (x(x))(y);
        });
      });
      };
  
  var FactGen = function(fact) {
      return (function(n) {
        return ((n == 0) ? 1 : (n * fact(n - 1)));
      });
      };
  fibonacci_y_combinator = (Y(FactGen))
  
  function Ymem(F, cache) {
    if (!cache) cache = {}; // Create a new cache.
    return function(arg) {
      if (cache[arg]) return cache[arg]; // Answer in cache.
      var answer = (F(function(n) {
        return (Ymem(F, cache))(n);
      }))(arg); // Compute the answer.
      cache[arg] = answer; // Cache the answer.
      return answer;
    };
  }
  
  var fibonacci_y_combinator_memoization = Ymem(function(g) {
    return (function(n) {
      if (n == 0) return 0;
      if (n == 1) return 1;
      return g(n - 1) + g(n - 2);
    });
  });
  
  
  function fibonacci_tail_recursion(n) {
      var calc = function(n, a, b) {
          return (n == 0 ) ? a : calc(n-1, b, a+b);
      };
      return calc(n, 0, 1);
  }
  
  function fibonacci_tail_recursion2(n) {
        var calc = function ( n, a, b, c ) {
                if ( n == 0 ) return b; var c=a+b;
                return ( n & 1 ) 
                        ? calc( n >> 1, b*(a+c)  , b*b + c*c )
                        : calc( n >> 1, a*a + b*b, b*(a+c)   );
        };
      return calc(n, 1, 0);
  }
  
  
  function fibonacci_loop2(n) {
        
        for(var a=1,b=0,c=1;n;n>>=1) {
                var abc=b*(a+c), bb=b*b; 
                if( n & 1 ) {
                        a = abc;
                        b = bb+c*c;
                } else {
                        a = bb+a*a;
                        b = abc;
                }
                c = a+b;                
        }
        return b;       
  }
</script>

Test runner

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

Java applet disabled.

var result = fibonacci_recursive(index);

var result = fibonacci_loop(index);

var result = fibonacci_direct(index);

var result = fibonacci_round(index);

var result = fibonacci_direct2(index);

var result = fibonacci_round2(index);

var result = fibonacci_recursive_memoization(index)

var result = fibonacci_y_combinator(index)

var result = fibonacci_y_combinator_memoization(index)

var result = fibonacci_tail_recursion(index);

var result = fibonacci_tail_recursion2(index);

var result = fibonacci_loop2(index);

Compare results of other browsers

Revisions

You can edit these tests or add even more tests to this page by appending /edit to the URL. Here’s a list of current revisions for this page:

• Revision 1: published by Kristof Neirynck on 11th June 2011
• Revision 2: published by Kristof Neirynck on 31st August 2011
• Revision 3: published by gerard_ on 6th September 2011
• Revision 4: published on 6th September 2011 and last updated on 7th September 2011

0 comments