Recursive and Memoized Y-Combinator Fibonnaci Functions

gistfile1.txt

// timer
// console.time('fib');
// console.timeEnd('fib');

//Recursive fibonnaci
var fib_recur = function (n) {
 if (n == 0) return 0;
 if (n == 1) return 1;
 return fib_recur(n-1) + fib_recur(n-2);
};


//----------------------------------
// fib with memoization

var fib_memo = (function () {
    var memo = [0, 1];
    var fib = function (n) {
        var result = memo[n];
        if (typeof result !== 'number') {
            var x = n - 1;
            var y = n - 2;
            result = fib(x) + fib(y);
            memo[n] = result;
        }
        return result; 
    };
    return fib;
}());


//------------------------------------
// Fib with only Ycombinator

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 fib_ycomb = Y(function (g) { return (function (n) {
 if (n == 0) return 0;
 if (n == 1) return 1;
 return g(n-1) + g(n-2);
}); });



//------------------------------------
// Fib with Ycombinator and memoization, Ymem takes a functional and an (optional)
// cache of answers. It returns the fixed point of the functional
// that caches intermediate results.
  
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 fib = Ymem(function(g) { return (function (n) {
 if (n == 0) return 0;
 if (n == 1) return 1;
 return g(n-1) + g(n-2);
 }); 
});