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);
  }
</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);

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