The Y-combinator is one of those things in computer science that amaze even the deftest of programming masterminds. Its ability to automatically convert recursive functions to non-recursive functions is why Douglas Crockford calls it "one of the most strange and wonderful artifacts of computer science", and Sussman and Steele once said, "That this manages to work is truly remarkable".

So a truly-remarkable, wonderfully strange artifact of computer science that brings recursive functions to their knees must be massive and complex, right? No, not exactly. Its implementation in JavaScript is only nine, very odd, lines of code. They are as follows:

var Y = function(F) {   return (function (f) {     return f(f);   } (function (f) {     return F(function (x) {       return f(f)(x);     });   })); }

Here's how it works: it finds the "fixed point" of the function passed in as an argument. Fixed points offer another way to think about functions rather than recursion and iteration in the theory of computer programming. And it does this with only the use of anonymous function expressions, function applications, and variable references. Note that Y does not reference itself. In fact, all those functions are anonymous.

As you might have guessed, the Y-combinator came out of lambda calculus. It's actually derived with the help of another combinator called the U-combinator. Combinators are special higher-order functions that only use function application and earlier defined combinators to define a result from its input.

To demonstrate the Y-combinator, we'll again turn to the factorial problem, but we need to define the factorial function a little differently. Instead of writing a recursive function, we write a function that returns a function that is the mathematical definition of factorials. Then we can pass this into the Y-combinator.

var FactorialGen = function(factorial) {   return (function(n) {     if (n == 0) {       // base case       return 1;     }     else {       // recursive case       return n * factorial(n – 1);     }   }); }; Factorial = Y(FactorialGen); Factorial(10); // 3628800

However, when we give it a significantly large number, the stack overflows just as if tail recursion without trampolining was used.

Factorial(23456); // RangeError: Maximum call stack size exceeded

But we can use trampolining with the Y-combinator as in the following:

var FactorialGen2 = function (factorial) {   return function(n) {     var factorial = thunk(function (x, n) {       if (n == 0) {         return x;       }       else {         return factorial(n * x, n - 1);       }     });     return trampoline(factorial(1, n));   } };  var Factorial2 = Y(FactorialGen2) Factorial2(10); // 3628800 Factorial2(23456); // Infinity

We can also rearrange the Y-combinator to perform something called memoization.

Memoization

Memoization is the technique of storing the result of expensive function calls. When the function is later called with the same arguments, the stored result is returned rather than computing the result again.

Although the Y-combinator is much faster than recursion, it is still relatively slow. To speed it up, we can create a memoizing fixed-point combinator: a Y-like combinator that caches the results of intermediate function calls.

var Ymem = function(F, cache) {   if (!cache) {     cache = {} ; // Create a new cache.   }   return function(arg) {     if (cache[arg]) {       // Answer in cache       return cache[arg] ;      }     // else compute the answer     var answer = (F(function(n){       return (Ymem(F,cache))(n);     }))(arg); // Compute the answer.     cache[arg] = answer; // Cache the answer.     return answer;   }; }

So how much faster is it? By using , we can compare the performance.

The following results are with random numbers between 1 and 100. We can see that the memoizing Y-combinator is much, much faster. And adding trampolining to it does not slow it down by much. You can view the results and run the tests yourself at this URL: .

The bottom line is: the most efficient and safest method of performing recursion in JavaScript is to use the memoizing Y-combinator with tail-call elimination via trampolining and thunks.