memoized Y combinator, see very nice article at http://matt.might.net/articles/implementation-of-recursive-fixed-point-y-combinator-in-javascript-for-memoization/ derivation derived with help from http://blog.jcoglan.com/2008/01/10/deriving-the-y-combinator/

DerivingY.js

/*
Factorial of course. Can't talk about recursion without factorial.
*/
function basicFactorial(n) {
  return n === 0 ? 1 : n * basicFactorial(n-1);
}

/*
Define a *non-recursive* function that has the factorial function as a fixpoint.
*/
function prefact(f) {
  return function(n) {
    return n === 0 ? 1 : n * f(n-1);
  };
}

/*
prefact takes a function that gets used in the body of the function it returns.
Clearly, if we pass basic factorial to prefact, we will get factorial back:
*/
prefact(basicFactorial)(10) === basicFactorial(10);  // true


/*
But we could pass any old function whose output supports the "*" operator in there:
*/
prefact(function() { return 0; })
prefact(function() { return 0; })(100); // 0
prefact(function() { return 0; })(200); // 0
prefact(function() { return 0; })(50000); // 0
// etc.

/*
This is all a bit pointless in this case, since we have defined basicFactorial already,
so we don't need to go through this. But suppose we had not defined basicFactorial.
Wouldn't it be nice if there was a function that we could pass prefact to that would 
return the fixpoint of it, i.e. the factorial function?

That is what the Y combinator does.

Pass prefact to Y, and out comes the factorial function:
*/

Y(prefact)(100); // 9.33262154439441e+157; use caching Y combinator, as above ...

/*
Note that:
*/

Y(prefact)(100) === prefact(basicFactorial)(100)

/*
Or in other words:
*/

Y(prefact)(100) === prefact(Y(prefact))(100)

/*
So we did not need to define basic factorial *at all*, we let Y derive it
from the non-recursive function prefact. The nice thing about this is we are able to apply some 
optimization to the recursive function, viz. memoizing.

Let's look at it from the other direction now, and build up to Y.
We have our non-recursive functional prefact that we want to calculate the fixpoint of.
*/

function prefact(f) {
  return function(n) {
    return n === 0 ? 1 : n * f(n-1);
  };
}

/*
As noted above, pass the factorial function in, and prefact returns the factorial function.
It is a little unsatisfactory though, since we have pretty much defined factorial in the body 
of prefact--why not use that?

So here's our next try: Apply prefact to itself. This requires a small change to the body of prefact,
to self-apply the passed in function to get the body out and apply it to the inner argument.
*/

function prefact(f) {
  return function(n) {
    return n === 0 ? 1 : n * f(f)(n-1);  // if f is prefact, it will return the factorial function
  };
}
prefact(prefact)(5); // => 120


/*
Further transformation. We want to isolate the fixpoint function.
*/

function prefact(f) {
  return function(x) {
    var g = function(q) {
      return function(n) {
        return n === 0 ? 1 : n * q(n-1);
      };
    };
    return g(f(f))(x);
  };
}

/*
Since inner function g does not depend on anything in closure, we can pull it out. 
The pulled-out function may look familiar--it is the non-recursive version of the 
factorial function that we were calling "prefact" above. Now prefact has become 
*almost* completely abstract.
*/

function g(f) {
  return function(n) {
      return n === 0 ? 1 : n * f(n-1);
    };
  };
}
function prefact(f) {
  return function(x) {
    return g(f(f))(x);
  };
}
prefact(prefact)(5); // => 120

/*
So we've pulled g out of prefact, but prefact still depends on g. The final step is to
wrap prefact in a function that takes the functional "g" as an argument. Then prefact 
will have no dependencies.

So, let's wrap it in a function that takes our non-recursive factorial functional and returns
the fixpoint of it. And since this is the last step, let's call that function "Y".
*/

function Y(f) {
  var p = function(h) {        // abstracted prefact, now binding f to the passed in function
    return function(x) {
      return f(h(h))(x);
    };
  };
  return p(p);
}

Y(g)(6); // => 720

/*
Holy crap! it works! Better yet, it will provide a fixpoint for any unary function, e.g.
*/

function prefib(f) {
  return function(n) {
    return n < 2 ? n : f(n-1) + f(n-2); 
  };
}
Y(prefib)(10); // => 55

/*
The version above handles only single arguments. It would be more useful if it
were variadic.
*/

function Y(f) {
  var p = function(h) {
    return function() {
      return f(h(h)).apply(null, arguments);
    };
  };
  return p(p);
}

Y.js

/*
F is a functional, i.e. a function that takes a function. Y will take that functional 
and produce a fixed point for it
*/
function Y(F, cache) {
  cache = cache || {};
  return function(arg) {
    var answer;
    if (cache[arg]) {
      return cache[arg] ; // Answer in cache.
    }
    answer = (F(function(n) {
      return (Y(F, cache))(n);
    }))(arg);
    cache[arg] = answer; // Cache the answer.
    return answer;
  };
}

/*
This looks familiar, but something is different ...
*/
function mkFib(g) { 
  return function (n) {
    return n < 2 ? n : g(n-1) + g(n-2) ;
  }; 
}

/*
Pass mkFib to Y get back the fixed point of mkFib, i.e. the Fibonacci function!
*/
var fib = Y(mkFib);

/* 
this is virtually instantaneous. Don't try to compare vs. recursive 
fib unless you want to wait a real long time. 
*/
fib(100);  // 354224848179262000000

/*
Factorial example:
*/
function mkFact(g) {
  return function(n) {
    return n === 0 ? 1 : n * g(n - 1);
  };
}

YvariadicAndCaching.js

/*
here is the unary version
*/
function Y(f) {
  var p = function(h) {
    return function(x) {
      return f(h(h))(x);
    };
  };
  return p(p);
}

/*
here is the memoized unary Y:
*/
function Y(f, cache) {
  cache = cache || {};
  var p = function(h) {
    return function(x) {
      var answer;
      if (cache[x]) {
        return cache[x];
      } 
      answer = f(h(h))(x);
      cache[x] = answer;
      return answer;
    };
  };
  return p(p);
}

/*
here's the variadic Y we derived above:
*/
function Y(f) {
  var p = function(h) {
    return function() {
      return f(h(h)).apply(null, arguments);
    };
  };
  return p(p);
}

/*
to memoize this we have to handle multiple arguments in the cache.
We define a helper function joinArgs to help with this
*/
function joinArgs(args, delim) {
  return Array.prototype.join.call(args, delim);
}

function Y(f, cache) {
  var p, delim = "|*";
  cache = cache || {};
  p = function(h) {
    return function() {
      var answer, argstr = joinArgs(arguments, delim);
      if (cache[argstr]) {
        return cache[argstr];
      }
      answer = f(h(h)).apply(null, arguments);
      cache[argstr] = answer;
      return answer;
    };
  };
  return p(p);
}

zzzzCache.js

// per paulg: this one is faster than Function.call.bind(Array.prototype.join) and 
// JSON.stringify *AND* it works in IE (see: http://jsperf.com/fcb-vs-json):
var joinargs = function (args, delimiter) { 
  return Array.prototype.join.call(args, delimiter); 
};