下面是Y-Combinator和Factorial函数的JavaScript实现(来自Douglas Crockford的文章，可在http://javascript.crockford.com/little.html上找到)。

function Y(le) {
    return (function (f) {
        return f(f);
    }(function (f) {
        return le(function (x) {
            return f(f)(x);
        });
    }));
}

var factorial = Y(function (fac) {
    return function (n) {
        return n <= 2 ? n : n * fac(n - 1);
    };
});

var number120 = factorial(5);

对于那些没有深入接触过函数式编程，现在也不想开始，但有点好奇的程序员:

Y组合子是一个公式，它允许你在这样的情况下实现递归:函数不能有名称，但可以作为参数传递，用作返回值，并在其他函数中定义。

它的工作原理是将函数作为参数传递给自己，这样它就可以调用自己。

它是lambda演算的一部分，lambda演算实际上是数学，但实际上是一种编程语言，是计算机科学尤其是函数式编程的基础。

Y组合子的日常实用价值是有限的，因为编程语言倾向于让你命名函数。

如果你需要在警察的队列中识别它，它看起来是这样的:

Y = λf.(λx。F (x x)) (λx。F (x x))

你通常可以发现它，因为重复的(λx。F (x x))

λ符号是希腊字母，这是λ演算的名字，有很多(λx.t)风格的术语因为这就是λ演算的样子。

如果你准备好长篇大论，Mike Vanier有一个很好的解释。长话短说，它允许您在一种不一定支持递归的语言中实现递归。

Y-combinator是一个“函数”(一个作用于其他函数的函数)，当你不能从内部引用函数时，它可以实现递归。在计算机科学理论中，它概括了递归，抽象了递归的实现，从而将递归与函数的实际工作分离开来。递归函数不需要编译时名称的好处是一种额外的好处。=）

这适用于支持lambda函数的语言。lambdas基于表达式的特性通常意味着它们不能通过名称引用自己。通过声明变量，引用它，然后赋值给它，来完成自引用循环，是很脆弱的。可以复制lambda变量，并重新分配原始变量，这将破坏自引用。

y组合子在静态类型语言(过程性语言通常如此)中实现起来很麻烦，而且经常使用起来也很麻烦，因为通常类型限制要求在编译时知道函数的参数数量。这意味着必须为需要使用的任何参数count编写y-combinator。

下面是一个在c#中如何使用和工作的Y-Combinator的例子。

使用y组合子涉及到一种构造递归函数的“不寻常”方式。首先，你必须把你的函数写成一段代码，调用一个已经存在的函数，而不是它自己:

// Factorial, if func does the same thing as this bit of code...
x == 0 ? 1: x * func(x - 1);

然后将其转换为一个函数，该函数接受一个要调用的函数，并返回一个这样做的函数。这被称为函数，因为它接受一个函数，并对其执行一个操作，该操作产生另一个函数。

// A function that creates a factorial, but only if you pass in
// a function that does what the inner function is doing.
Func<Func<Double, Double>, Func<Double, Double>> fact =
  (recurs) =>
    (x) =>
      x == 0 ? 1 : x * recurs(x - 1);

现在你有了一个函数，它接受一个函数，并返回另一个函数，它看起来像一个阶乘，但它不是调用它自己，而是调用传递给外部函数的参数。怎么把它变成阶乘呢?将内部函数传递给自身。Y-Combinator就是这样做的，它是一个具有永久名称的函数，可以引入递归。

// One-argument Y-Combinator.
public static Func<T, TResult> Y<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> F)
{
  return
    t =>  // A function that...
      F(  // Calls the factorial creator, passing in...
        Y(F)  // The result of this same Y-combinator function call...
              // (Here is where the recursion is introduced.)
        )
      (t); // And passes the argument into the work function.
}

不是阶乘调用自身，而是阶乘调用阶乘生成器(由对Y-Combinator的递归调用返回)。根据t的当前值，从生成器返回的函数会再次调用生成器，用t - 1，或者直接返回1，终止递归。

它是复杂而神秘的，但在运行时，它的工作关键是“延迟执行”，并将递归分解为跨越两个函数。内部的F作为参数传递，仅在必要时才在下一次迭代中调用。

我想知道从头开始建立这个系统是否有任何用处。让我们来看看。这是一个基本的递归阶乘函数:

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

让我们重构并创建一个名为fact的新函数，它返回一个匿名的阶乘计算函数，而不是执行计算本身:

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

var factorial = fact();

这有点奇怪，但这没什么问题。我们只是在每一步生成一个新的阶乘函数。

这个阶段的递归仍然相当明确。事实函数需要知道自己的名字。让我们参数化递归调用:

function fact(recurse) {
    return function(n) {
        return n == 0 ? 1 : n * recurse(n - 1);
    };
}

function recurser(x) {
    return fact(recurser)(x);
}

var factorial = fact(recurser);

这很好，但是递归仍然需要知道自己的名字。让我们把它参数化:

function recurser(f) {
    return fact(function(x) {
        return f(f)(x);
    });
}

var factorial = recurser(recurser);

现在，我们不直接调用递归器(recurser)，而是创建一个包装器函数，返回它的结果:

function Y() {
    return (function(f) {
        return f(f);
    })(recurser);
}

var factorial = Y();

现在我们可以完全去掉递归的名字;它只是Y内部函数的一个参数，可以用函数本身替换:

function Y() {
    return (function(f) {
        return f(f);
    })(function(f) {
        return fact(function(x) {
            return f(f)(x);
        });
    });
}

var factorial = Y();

唯一仍然引用的外部名称是fact，但现在应该清楚了，它也很容易参数化，创建完整的，通用的解决方案:

function Y(le) {
    return (function(f) {
        return f(f);
    })(function(f) {
        return le(function(x) {
            return f(f)(x);
        });
    });
}

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

我认为回答这个问题的最好方法是选择一种语言，比如JavaScript:

function factorial(num)
{
    // If the number is less than 0, reject it.
    if (num < 0) {
        return -1;
    }
    // If the number is 0, its factorial is 1.
    else if (num == 0) {
        return 1;
    }
    // Otherwise, call this recursive procedure again.
    else {
        return (num * factorial(num - 1));
    }
}

现在重写它，使它不使用函数内部的函数名，但仍然递归地调用它。

函数名factorial唯一应该看到的地方是在调用位置。

提示:不能使用函数名，但可以使用参数名。

解决这个问题。不要去查。一旦你解决了它，你就会明白y组合子解决了什么问题。