Y Combinator in JavaScript

On Wikipedia the Y Combinator article begins like this:

A fixed point combinator (or fixed-point operator) is a higher-order function which computes a fixed point of other functions. This operation is relevant in programming language theory because it allows the implementation of recursion in the form of a rewrite rule, without explicit support from the language's runtime engine.

An easier way to understand the Y combinator is that we can create recursive functions without explicit support for recursion, we only need high-order functions to have recursion... Now I am going to show you how this is possible in JavaScript.

The factorial function can be defined like this:

function fac(n) {
    return n == 0 ? 1 : n * fac(n - 1);
}
alert(fac(5)); //120

As you see it calls itself recursively. But we can also implement factorial without calling fac explicitly:

function facMaker(fn) {
    return function(n) {
        return n == 0 ? 1 : n * fn(fn)(n - 1);
    }
}
var fac1 = facMaker(facMaker);
alert(fac1(5)); //120

Two things to notice:

• facMaker(facMaker): We pass facMaker to itself!
• fn(fn)(n - 1): We expand facMaker by calling fn(fn). By our definition fn(fn) returns a function which takes an integer.

This is what facMaker(facMaker) really does:

var fac2 = function(fn) {
    return function(n) {
        return n == 0 ? 1 : n * fn(fn)(n - 1);
}}(function(fn) {
    return function(n) {
        return n == 0 ? 1 : n * fn(fn)(n - 1);
}});
alert(fac2(5)); //120

This rewrite trick is essentially what a Y Combinator does, i.e. a Y Combinator takes a function and turns it in a recursive function!

Y Combinator implemented in JavaScript looks like this:

function Y(dn) {
    return function(fn) {
        return fn(fn);
    }(function(fn) {
        return dn(function(x) {
            return fn(fn)(x);
        });
    });
}

And more generally like this:

function Y(dn) {
    return function(fn) {
        return fn(fn);
    }(function(fn) {
        return dn(function() {
            return fn(fn).apply(null, arguments);
        });
    });
}

We can implement factorial like this using a Y Combinator:

var fac3 = Y(function(fn) {
    return function(n) {
        return n == 0 ? 1 : n * fn(n - 1);
    }
});

Beautiful, but not that useful :)

Update:
I was a bit more gung ho about the Y Combinator and I stumbled upon The Why of Y note. It explains the Y Combinator in more detail:

Did you ever wonder how Y works and how anyone could ever have thought of it? In this note I'll try to explain to you not only how it works, but how someone could have invented it. I'll use Scheme notation because it is easier to understand when functions passed as arguments are being applied.