以下是对尼古拉斯·曼库索(Nicholas Mancuso)在回答中提到的文章(完全值得一读)中提到的原始问题的回答，以及其他答案:

什么是y组合子?

y组合子是一个“函数”(或高阶函数——一个作用于其他函数的函数)，它接受一个参数，这是一个非递归的函数，并返回该函数的一个递归版本。

---

有点递归=)，但更深入的定义:

一个组合子-就是一个没有自由变量的lambda表达式。 自由变量-是一个变量，不是一个约束变量。 绑定变量—包含在lambda表达式体中的变量，该变量名作为其参数之一。

另一种思考方式是，combinator是这样一个lambda表达式，在其中，你可以在任何地方用它的定义替换一个组合子的名称，并且一切都仍然有效(如果combinator在lambda体中包含对自身的引用，你将进入一个无限循环)。

y组合子是一个定点组合子。

函数的不动点是函数定义域中映射到函数自身的一个元素。 也就是说，如果f(c) = c, c是函数f(x)的一个不动点 这意味着f(f(…f(c)…))= fn(c) = c

组合符是如何工作的?

下面的例子假设强+动态类型:

惰性(正规阶)y组合子: 此定义适用于具有lazy(也称为deferred, call-by-need)求值的语言——该求值策略将表达式的求值延迟到需要它的值时。

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

这意味着，对于给定的函数f(它是非递归函数)，可以通过计算λx得到对应的递归函数。F (x x)然后把这个表达式应用到自身上。

严格(应用阶)y组合子: 这个定义适用于具有严格求值策略(也包括热切求值和贪婪求值策略)的语言，在这种策略中，表达式一旦绑定到变量就会被求值。

Y = λf.(λx.f(λy.((x x) y))) (λx.f(λy.((x x) y))) = λf.(λx.(x x)) (λx.f(λy.((x x) y)))

它本质上和lazy一样，只是有一个额外的λ包装器来延迟lambda的体计算。我问了另一个问题，和这个话题有点相关。

它们有什么用?

借用Chris Ammerman的回答:Y-combinator泛化递归，抽象其实现，从而将其与函数的实际工作分离。

尽管Y-combinator有一些实际应用，但它主要是一个理论概念，理解它将扩展你的整体视野，并有可能提高你的分析和开发技能。

它们在过程语言中有用吗?

正如Mike Vanier所说:在许多静态类型的语言中都可以定义Y组合子，但是(至少在我看到的例子中)这样的定义通常需要一些不明显的类型技巧，因为Y组合子本身没有直接的静态类型。这超出了本文的范围，所以我不再进一步提及

正如Chris Ammerman所提到的:大多数过程式语言都有静态类型。

所以这个问题的答案是，不是真的。

我从http://www.mail-archive.com/boston-pm@mail.pm.org/msg02716.html中引用了这个，这是我几年前写的一个解释。

在本例中我将使用JavaScript，但许多其他语言也可以。

我们的目标是写出一个1的递归函数 变量只使用1变量的函数，没有 赋值，通过名称定义事物等(为什么这是我们的 目标是另一个问题，我们把它作为 我们所面临的挑战。)似乎不可能，是吧?作为 举个例子，让我们实现阶乘。

第一步是说我们可以很容易地做到这一点，如果我们 作弊了一点。使用二元函数和 我们至少可以避免使用 赋值来建立递归。

// Here's the function that we want to recurse.
X = function (recurse, n) {
  if (0 == n)
    return 1;
  else
    return n * recurse(recurse, n - 1);
};

// This will get X to recurse.
Y = function (builder, n) {
  return builder(builder, n);
};

// Here it is in action.
Y(
  X,
  5
);

现在我们看看能不能少作弊。首先我们用 任务，但我们不需要。我们可以写成X和 Y内联。

// No assignment this time.
function (builder, n) {
  return builder(builder, n);
}(
  function (recurse, n) {
    if (0 == n)
      return 1;
    else
      return n * recurse(recurse, n - 1);
  },
  5
);

但是我们用两个变量的函数来得到一个1的函数 变量。我们能解决这个问题吗?一个叫 Haskell Curry有一个巧妙的技巧，如果你有好的高阶 那么你只需要一个变量的函数。的 证明是你可以从函数2(或更多) 一般情况下)变量以1变量为纯粹 像这样的机械文本转换:

// Original
F = function (i, j) {
  ...
};
F(i,j);

// Transformed
F = function (i) { return function (j) {
  ...
}};
F(i)(j);

在那里……完全一样。(这个技巧叫做 “模仿”它的发明者。Haskell也是一种语言 以哈斯克尔·库里命名。把它归为无用的琐事。) 现在只要把这个变换应用到任何地方，我们就得到 我们的最终版本。

// The dreaded Y-combinator in action!
function (builder) { return function (n) {
  return builder(builder)(n);
}}(
  function (recurse) { return function (n) {
    if (0 == n)
      return 1;
    else
      return n * recurse(recurse)(n - 1);
  }})(
  5
);

尽管试一试。Alert()返回，将其绑定到一个按钮，等等。 该代码不使用，递归地计算阶乘 2变量的赋值、声明或函数。(但 试图追踪它是如何工作的可能会让你头晕目眩。 递过来，没有推导，只是稍微重新格式化了一下 会导致代码令人困惑。)

可以将递归定义阶乘的4行替换为 任何你想要的递归函数。

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

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

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

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

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

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

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

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

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

下面是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-Combinator，我在Clojure和Scheme中都写了一份关于Y-Combinator的“傻瓜指南”。他们受到了《小阴谋家》的影响

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

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

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

作为一个组合子的新手，我发现Mike Vanier的文章(感谢Nicholas Mancuso)真的很有帮助。我想写一个总结，除了记录我的理解，如果它能对其他人有所帮助，我将非常高兴。

从糟糕到不那么糟糕

以factorial为例，我们使用下面的almost-factorial函数来计算number x的阶乘:

def almost-factorial f x = if iszero x
                           then 1
                           else * x (f (- x 1))

在上面的伪代码中，almost-阶乘接受函数f和数字x (almost-阶乘是curry的，所以它可以被视为接受函数f并返回一个1-arity函数)。

当almost-factorial计算x的阶乘时，它将x - 1的阶乘计算委托给函数f，并将该结果与x相加(在本例中，它将(x - 1)的结果与x相乘)。

它可以被看作是almost-阶乘接受了一个蹩脚的阶乘函数(它只能计算到数字x - 1)，并返回一个不那么蹩脚的阶乘(计算到数字x)。如下形式:

almost-factorial crappy-f = less-crappy-f

如果我们反复地将阶乘的不那么糟糕的版本传递给almost阶乘，我们最终会得到我们想要的阶乘函数f。其中可以考虑为:

almost-factorial f = f

Fix-point

几乎阶乘f = f意味着f是几乎阶乘函数的定点。

这是一种非常有趣的方式来看待上述函数之间的关系，对我来说是一个顿悟的时刻。(如果你还没读过，请阅读Mike关于fix-point的文章)

三个函数

概括地说，我们有一个非递归函数fn(就像我们的几乎阶乘)，我们有它的定点函数fr(就像我们的f)然后Y所做的是当你给Y fn, Y返回fn的定点函数。

总之(通过假设fr只有一个参数来简化;X退化为X - 1, X - 2…在递归):

我们将核心计算定义为fn: def fn fr x =…将x与result from (fr (- x1))累加，这是一个几乎有用的函数-尽管我们不能直接在x上使用fn，但它很快就会有用。这个非递归fn使用一个函数fr来计算它的结果 fnfr = fr, fr是Fn的定点，fr是有用的函数，我们可以用fr作用于x来得到结果 Y fn = fr, Y返回一个函数的定点，Y把我们几乎有用的函数fn变成有用的fr

推导Y(不含)

我将跳过Y的推导，直接去理解Y。Mike Vainer的帖子有很多细节。

Y的形式

Y定义为(lambda微积分格式):

Y f = λs.(f (s s)) λs.(f (s s))

如果我们替换函数左边的变量s，我们得到

Y f = λs.(f (s s)) λs.(f (s s))
=> f (λs.(f (s s)) λs.(f (s s)))
=> f (Y f)

所以(yf)的结果就是f的定点。

(yf)为什么成立?

根据f的特征，(Y f)可以是任意arity的函数，为了简化，我们假设(Y f)只带一个参数，就像我们的阶乘函数一样。

def fn fr x = accumulate x (fr (- x 1))

因为fn fr = fr，我们继续

=> accumulate x (fn fr (- x 1))
=> accumulate x (accumulate (- x 1) (fr (- x 2)))
=> accumulate x (accumulate (- x 1) (accumulate (- x 2) ... (fn fr 1)))

当最里面的(fn fr 1)是基本情况并且fn在计算中不使用fr时，递归计算终止。

再看一下Y:

fr = Y fn = λs.(fn (s s)) λs.(fn (s s))
=> fn (λs.(fn (s s)) λs.(fn (s s)))

So

fr x = Y fn x = fn (λs.(fn (s s)) λs.(fn (s s))) x

对我来说，这种设置的神奇之处在于:

fn and fr interdepend on each other: fr 'wraps' fn inside, every time fr is used to calculate x, it 'spawns' ('lifts'?) an fn and delegates the calculation to that fn (passing in itself fr and x); on the other hand, fn depends on fr and uses fr to calculate result of a smaller problem x-1. At the time fr is used to define fn (when fn uses fr in its operations), the real fr is not yet defined. It's fn which defines the real business logic. Based on fn, Y creates fr - a helper function in a specific form - to facilitate the calculation for fn in a recursive manner.

它帮助我现在这样理解Y，希望有帮助。

顺便说一句，我还发现《通过Lambda微积分介绍函数式编程》这本书非常好，我只读了一部分，事实上，我无法理解书中的Y，这让我想到了这篇文章。