# fibonacci (v4)

## Description

Testing out how slow recursion actually is.

## Preparation HTML

``````<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.
return (Ymem(F, cache))(n);
};
}

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

Testing in
TestOps/sec
recursive
``var result = fibonacci_recursive(index);``
loop
``var result = fibonacci_loop(index);``
direct
``var result = fibonacci_direct(index);``
round
``var result = fibonacci_round(index);``
direct2
``var result = fibonacci_direct2(index);``
round2
``var result = fibonacci_round2(index);``
recursive with memoization
``var result = fibonacci_recursive_memoization(index)``
Y combinator
``var result = fibonacci_y_combinator(index)``
Y combinator with memoization
``var result = fibonacci_y_combinator_memoization(index)``
tail recursion
``var result = fibonacci_tail_recursion(index);``
``var result = fibonacci_tail_recursion2(index);``
``var result = fibonacci_loop2(index);``