为了帮助自己掌握Y-Combinator，我在Clojure和Scheme中都写了一份关于Y-Combinator的“傻瓜指南”。他们受到了《小阴谋家》的影响

在方案: https://gist.github.com/z5h/238891

Clojure: https://gist.github.com/z5h/5102747

这两个教程都是代码中穿插的注释，应该剪切和粘贴到您最喜欢的编辑器。

为了帮助自己掌握Y-Combinator，我在Clojure和Scheme中都写了一份关于Y-Combinator的“傻瓜指南”。他们受到了《小阴谋家》的影响

在方案: https://gist.github.com/z5h/238891

Clojure: https://gist.github.com/z5h/5102747

这两个教程都是代码中穿插的注释，应该剪切和粘贴到您最喜欢的编辑器。

JavaScript中的y组合子:

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

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

factorial(5)  // -> 120

编辑: 通过查看代码，我学到了很多东西，但是如果没有一些背景知识，这个代码有点难以理解——对此我感到抱歉。有了其他答案提供的一些常识，你就可以开始分析正在发生的事情了。

The Y function is the "y-combinator". Now take a look at the var factorial line where Y is used. Notice you pass a function to it that has a parameter (in this example, recurse) that is also used later on in the inner function. The parameter name basically becomes the name of the inner function allowing it to perform a recursive call (since it uses recurse() in it's definition.) The y-combinator performs the magic of associating the otherwise anonymous inner function with the parameter name of the function passed to Y.

关于Y如何变魔术的完整解释，请查看链接文章(顺便说一下，不是我写的)。

Y-Combinator是通量电容器的另一个名称。

上面的大多数答案描述了y组合子是什么，但没有描述它的用途。

用不动点组合子来证明lambda演算是图灵完备的。这是计算理论中一个非常重要的结果，为函数式编程提供了理论基础。

学习不动点组合子也帮助我真正理解了函数式编程。但我从未发现它们在实际编程中有任何用处。

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作为参数传递，仅在必要时才在下一次迭代中调用。