什么是 Y 组合器？

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

想要改进这个问题吗？通过编辑这篇文章来更新问题，使其仅关注一个问题。

5 年前已关闭。

Answer 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-combinator 解决了什么问题。

Answer 2

y 组合器实现匿名递归。 因此

function fib( n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }

而不是您当然可以执行

function ( fib, n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }

，y 组合器仅适用于按名称调用语言， 的操作。 如果您想在任何正常的按值调用语言中使用它，那么您将需要相关的 z 组合器（y 组合器将发散/无限循环）。

Answer 3

this 运算符可以简化您的生活：

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

然后您可以避免额外的函数：

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

最后，您调用 fac(5)。

Answer 4

定点组合器（或定点运算符）是计算其他函数的定点的高阶函数。 此操作与编程语言理论相关，因为它允许以重写规则的形式实现递归，而无需语言运行时引擎的显式支持。 （src 维基百科）

Answer 5

以下是原始问题的答案，编译自文章（完全值得一读）尼古拉斯·曼库索的回答< /a>，以及其他答案：

什么是 Y 组合器？

Y 组合器是一个“函数”（或高阶函数 - 对其他函数进行操作的函数），它采用单个参数（非递归函数），并返回该函数的版本递归的。

---

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

组合器——只是一个没有自由变量的 lambda 表达式。

自由变量——是不是绑定变量的变量。

绑定变量 — 包含在 lambda 表达式主体内的变量，该表达式将该变量名称作为其参数之一。

另一种思考方式是，组合器是这样一个 lambda 表达式，在其中，您可以在找到组合器的任何地方用其定义替换组合器的名称，并且一切仍然有效（如果组合器在 lambda 体内包含对其自身的引用）。

Y-组合器是一个定点组合器。

函数的不动点是函数域中由函数映射到其自身的元素。

也就是说，如果f(c) = c，c是函数f(x)的不动点

这意味着f(f(...f(c)...)) = fn(c) = c

组合器如何工作？

下面的示例假设强+动态输入：

惰性（正序）Y 组合器：

此定义适用于具有惰性（也称为延迟、按需调用）求值的语言 - 求值策略延迟表达式的求值，直到需要其值为止。

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

这意味着，对于给定的函数f（非递归函数），可以先通过计算λx.f(xx)得到对应的递归函数，然后应用这个 lambda 表达式本身。

严格（应用顺序）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)))

它与惰性求值相同从本质上讲，它只是有一个额外的 λ 包装器来延迟 lambda 的主体评估。 我问了另一个问题，有点与此主题相关。

它们有什么用处？

被盗借自Chris Ammerman的回答：Y-combinator概括递归，抽象其实现，从而将其与相关函数的实际工作分开。

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

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

正如 Mike Vanier 所说的所述：可以定义一个 Y 组合器在许多静态类型语言中，但是（至少在我见过的示例中）这样的定义通常需要一些不明显的类型黑客，因为 Y 组合器本身没有简单的静态类型。 这超出了本文的范围，因此我不会进一步提及

正如 Chris Ammerman 提到的：大多数过程语言具有静态类型。

所以回答这个问题——不是真的。

Answer 6

作为组合器的新手，我发现 Mike Vanier 的文章（感谢 Nicholas Mancuso）非常有帮助。 我想写一个总结，除了记录我的理解之外，如果能对其他人有帮助我会很高兴。

从蹩脚到少蹩脚

以阶乘为例，我们使用以下almost-factorial函数来计算数字x<的阶乘/code>：

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

在上面的伪代码中，almost-factorial 接受函数 f 和数字 x (almost-factorial< /code> 是柯里化的，因此它可以被视为接受函数 f 并返回一个 1 元函数）。

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

它可以被视为almost-factorial采用阶乘函数的蹩脚版本（只能计算到数字x - 1）并返回阶乘的不太蹩脚版本（计算到数字x）。 就像这种形式一样：

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

如果我们重复地将阶乘的less-crappy版本传递给almost-factorial，我们最终将得到我们想要的阶乘函数f。 可以将其视为：

almost-factorial f = f

定点

事实上，几乎阶乘 f = f 意味着 f 是函数 < 的定点代码>几乎阶乘。

这是查看上述函数之间关系的一种非常有趣的方式，这对我来说是一个顿悟的时刻。 （如果您还没有阅读过，请阅读 Mike 关于定点的文章）

三个函数

概括来说，我们有一个非递归函数 fn （就像我们的近似阶乘），我们有它的定点函数fr（就像我们的f），那么Y所做的就是当你给出Y时> fn, Y 返回fn 的定点函数。

总而言之（通过假设 fr 仅采用一个参数来简化；x 退化为 x - 1、x - 2...在递归中）：

• 我们将核心计算定义为fn：def fn fr x = ...accumulate x结果来自 (fr (- x 1))，这是几乎有用函数 - 尽管我们不能使用 fn直接在 x 上，很快就会有用。 这个非递归fn使用函数fr来计算其结果
• fn fr = fr，fr 是fn的不动点，fr是有用函数，我们可以使用< code>fr 在 x 上获取结果
• Y fn = fr，Y 返回修复结果- 函数的点，Y 将我们的几乎有用函数fn变成有用 fr

推导Y（不包括）

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

Y Y 的形式

定义为（以 lambda calculus 格式）：

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)

所以，(Y f) 的结果确实是 f 的不动点。

为什么 (Y f) 有效？

根据 f 的签名，(Y f) 可以是任意数量的函数，为了简化，我们假设 (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)))

所以

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

对我来说，此设置的神奇部分是：

• fn 和 fr 相互依赖：fr '包裹' fn 内部，每次使用 fr 计算 x 时，它都会“生成”（“提升”？）一个 fn 并将计算委托给该 fn（传入 fr 和 x 本身）； 另一方面，fn 依赖于 fr 并使用 fr 计算较小问题 x-1 的结果。
• 当 fr 用于定义 fn 时（当 fn 在其操作中使用 fr 时），真正的 < code>fr 尚未定义。
• fn 定义了真正的业务逻辑。 在fn的基础上，Y创建了fr——一个特定形式的辅助函数——以方便计算fn以递归方式。

它帮助我现在以这种方式理解Y，希望它有所帮助。

顺便说一句，我还发现这本书通过 Lambda Calculus 进行函数式编程简介非常好，我只读了一部分，事实上我无法理解书中的 Y，这导致我写了这篇文章。

Answer 7

Y 组合器是磁通电容器的别称。

Answer 8

我在 Clojure 和 Scheme 中写了一份 Y-Combinator 的“白痴指南”，以帮助自己掌握它。 他们受到“小阴谋家”中的材料的影响

：计划中：
https://gist.github.com/z5h/238891

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

两个教程都是代码，中间散布着注释并且应该被切割& 可粘贴到您最喜欢的编辑器中。

Answer 9

其他答案对此提供了非常简洁的答案，但没有一个重要的事实：您不需要以这种复杂的方式用任何实用语言实现定点组合器，这样做没有任何实际目的（除了“看，我知道 Y 组合器是什么”）是”）。 这是重要的理论概念，但实用价值不大。

Answer 10

下面是 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);

Answer 11

匿名递归

定点组合器是一个高阶函数 fix，根据定义满足等价

forall f.  fix f  =  f (fix f)

fix f 表示固定点的解 x -点方程

               x  =  f x

自然数的阶乘可以通过使用fix来证明

fact 0 = 1
fact n = n * fact (n - 1)

，可以在没有匿名自指的情况下导出一般/μ-递归函数的任意构造性证明。

fact n = (fix fact') n

其中

fact' rec n = if n == 0
                then 1
                else n * rec (n - 1)

，

   fact 3
=  (fix fact') 3
=  fact' (fix fact') 3
=  if 3 == 0 then 1 else 3 * (fix fact') (3 - 1)
=  3 * (fix fact') 2
=  3 * fact' (fix fact') 2
=  3 * if 2 == 0 then 1 else 2 * (fix fact') (2 - 1)
=  3 * 2 * (fix fact') 1
=  3 * 2 * fact' (fix fact') 1
=  3 * 2 * if 1 == 0 then 1 else 1 * (fix fact') (1 - 1)
=  3 * 2 * 1 * (fix fact') 0
=  3 * 2 * 1 * fact' (fix fact') 0
=  3 * 2 * 1 * if 0 == 0 then 1 else 0 * (fix fact') (0 - 1)
=  3 * 2 * 1 * 1
=  6

这个正式证明

fact 3  =  6

有条不紊地使用定点组合子等价重写

fix fact'  ->  fact' (fix fact')

Lambda演算

无类型 lambda 演算形式主义包含上下文无关语法，

E ::= v        Variable
   |  λ v. E   Abstraction
   |  E E      Application

其中v 变量范围，以及 beta 和 eta 缩减 规则

(λ x. B) E  ->  B[x := E]                                 Beta
  λ x. E x  ->  E          if x doesn’t occur free in E   Eta

Beta 缩减替换抽象中变量 x 的所有自由出现（“函数”）主体 B 由表达式（“参数”）E 组成。 Eta 减少消除了多余的抽象。 有时在形式主义中会省略它。 不适用归约规则的不可约表达式采用正规或规范形式。

λ x y. E

的简写

λ x. λ y. E

是（抽象多重性）

E F G

，是

(E F) G

（应用程序左关联性）的简写，

λ x. x

并且

λ y. y

是 alpha 等价的。

抽象和应用是 lambda 演算的两个唯一的“语言原语”，但它们允许对任意复杂的数据和操作进行编码。

丘奇数字是自然数的编码，类似于皮亚诺公理自然数。

   0  =  λ f x. x                 No application
   1  =  λ f x. f x               One application
   2  =  λ f x. f (f x)           Twofold
   3  =  λ f x. f (f (f x))       Threefold
    . . .

SUCC  =  λ n f x. f (n f x)       Successor
 ADD  =  λ n m f x. n f (m f x)   Addition
MULT  =  λ n m f x. n (m f) x     Multiplication
    . . .

形式证明

1 + 2  =  3

使用 beta 约简重写规则的

   ADD                      1            2
=  (λ n m f x. n f (m f x)) (λ g y. g y) (λ h z. h (h z))
=  (λ m f x. (λ g y. g y) f (m f x)) (λ h z. h (h z))
=  (λ m f x. (λ y. f y) (m f x)) (λ h z. h (h z))
=  (λ m f x. f (m f x)) (λ h z. h (h z))
=  λ f x. f ((λ h z. h (h z)) f x)
=  λ f x. f ((λ z. f (f z)) x)
=  λ f x. f (f (f x))                                       Normal form
=  3

：组合器

在 lambda 演算中，组合器是不包含自由变量的抽象。 组合器

λ x. x

最简单的是：I，与恒等函数同构的恒等

id x = x

此类组合器是像 SKI 系统这样的组合器演算的原始算子。

S  =  λ x y z. x z (y z)
K  =  λ x y. x
I  =  λ x. x

Beta 减少并不是强烈标准化； 并非所有可约表达式“redexes”都会在 beta 约简下收敛到正常形式。 一个简单的例子是 omega ω 组合器

λ x. x x

对其自身的发散应用：

   (λ x. x x) (λ y. y y)
=  (λ y. y y) (λ y. y y)
. . .
=  _|_                     Bottom

优先考虑减少最左边的子表达式（“头”）。 应用顺序在替换之前规范参数，正常顺序则不然。 这两种策略类似于急切求值（例如 C）和惰性求值（例如 Haskell）。

   K          (I a)        (ω ω)
=  (λ k l. k) ((λ i. i) a) ((λ x. x x) (λ y. y y))

在急切的应用阶 beta 约简下发散

=  (λ k l. k) a ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ y. y y) (λ y. y y))
. . .
=  _|_

由于在严格语义中，

forall f.  f _|_  =  _|_

，但在惰性正序 beta 约简下收敛

=  (λ l. ((λ i. i) a)) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  a

如果一个表达式具有范式，则正常阶 beta 约简将会找到它。

Y

Y 定点组合器的基本属性

λ f. (λ x. f (x x)) (λ x. f (x x))

由下式给出

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

：等价性

Y g  =  g (Y g)

同构于

fix f  =  f (fix f)

无类型 lambda 演算可以对一般/μ-递归函数上的任意构造性证明进行编码。

 FACT  =  λ n. Y FACT' n
FACT'  =  λ rec n. if n == 0 then 1 else n * rec (n - 1)

   FACT 3
=  (λ n. Y FACT' n) 3
=  Y FACT' 3
=  FACT' (Y FACT') 3
=  if 3 == 0 then 1 else 3 * (Y FACT') (3 - 1)
=  3 * (Y FACT') (3 - 1)
=  3 * FACT' (Y FACT') 2
=  3 * if 2 == 0 then 1 else 2 * (Y FACT') (2 - 1)
=  3 * 2 * (Y FACT') 1
=  3 * 2 * FACT' (Y FACT') 1
=  3 * 2 * if 1 == 0 then 1 else 1 * (Y FACT') (1 - 1)
=  3 * 2 * 1 * (Y FACT') 0
=  3 * 2 * 1 * FACT' (Y FACT') 0
=  3 * 2 * 1 * if 0 == 0 then 1 else 0 * (Y FACT') (0 - 1)
=  3 * 2 * 1 * 1
=  6

（乘法延迟，汇合）

对于丘奇无类型 lambda 演算，已证明除了 Y 之外还存在递归可枚举的定点组合器。

 X  =  λ f. (λ x. x x) (λ x. f (x x))
Y'  =  (λ x y. x y x) (λ y x. y (x y x))
 Z  =  λ f. (λ x. f (λ v. x x v)) (λ x. f (λ v. x x v))
 Θ  =  (λ x y. y (x x y)) (λ x y. y (x x y))
  . . .

正态阶 beta 约简使得未扩展的无类型 lambda 演算成为图灵完备的重写系统。

在 Haskell 中，定点组合器可以优雅地实现，

fix :: forall t. (t -> t) -> t
fix f = f (fix f)

在计算所有子表达式之前，Haskell 的惰性标准化为有限。

primes :: Integral t => [t]
primes = sieve [2 ..]
   where
      sieve = fix (\ rec (p : ns) ->
                     p : rec [n | n <- ns
                                , n `rem` p /= 0])

---

• David Turner：Church 的论文和函数式编程
• 阿隆佐教堂：一个无法解决的问题初等数论问题
• Lambda 演算
• 丘奇-罗瑟定理

Answer 12

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

定点组合器用于表明lambda 演算是图灵完备。 这是计算理论中非常重要的结果，为函数式编程提供了理论基础。

研究定点组合器也帮助我真正理解了函数式编程。 但我从未在实际编程中发现它们有任何用处。

Answer 13

对于没有深入接触过函数式编程，并且不想现在开始，但有一点好奇的程序员：

Y 组合子是一个公式，它可以让你在函数可以实现递归的情况下实现递归。没有名称，但可以作为参数传递、用作返回值以及在其他函数中定义。

它的工作原理是将函数作为参数传递给自身，以便它可以调用自身。

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

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

如果您需要在警察阵容中识别它，它看起来像这样：

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

由于重复的(λx.f (xx))，您通常可以发现它。

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

Answer 14

JavaScript 中的 y-combinator：

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

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

Y 函数是“y 组合器”。 现在看一下使用 Y 的 var Factorial 行。 请注意，您向其传递了一个具有参数的函数（在本示例中为 recurse），该参数稍后也会在内部函数中使用。 参数名称基本上成为内部函数的名称，允许它执行递归调用（因为它在定义中使用了recurse()。）y-combinator 执行了关联匿名内部函数的魔力。函数的参数名称传递给 Y。

有关 Y 如何发挥魔法的完整说明，请查看 链接文章（顺便说一句，不是我写的。）

Answer 15

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

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();

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

这个阶段的递归仍然相当明确。 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);

这很好，但是 recurser 仍然需要知道它自己的名称。 我们也将其参数化：

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

var factorial = recurser(recurser);

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

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

var factorial = Y();

我们现在可以去掉 recurser 名称共; 它只是 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);
    };
});

Answer 16

Y 组合器是一种“函数式”（对其他函数进行操作的函数），当您无法从函数内部引用该函数时，它可以启用递归。 在计算机科学理论中，它概括了递归，抽象了其实现，从而将其与相关函数的实际工作分开。 递归函数不需要编译时名称的好处是一种额外的好处。 =)

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

在静态类型语言中，Y 组合器的实现和使用都很麻烦（ 过程语言通常是这样的），因为通常类型限制需要相关函数的参数数量在编译时就知道。 这意味着必须为需要使用的任何参数计数编写 y 组合器。

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

Answer 17

如果您准备好阅读长篇文章，Mike Vanier 有一个很棒的解释。 长话短说，它允许您使用本身不一定支持递归的语言来实现递归。

Answer 18

我已从 http://www.mail-archive.com/ 中提取了此内容[email protected]/msg02716.html 这是我几年前写的解释。

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

我们的目标是能够编写 1 的递归函数
变量仅使用 1 个变量的函数，并且不使用
作业、按名称定义事物等（为什么这是我们的
目标是另一个问题，我们就以此为目标
我们面临的挑战。）似乎不可能，是吧？ 作为
举个例子，让我们实现阶乘。

第一步是说我们可以很容易地做到这一点，如果我们
欺骗了一点。 使用 2 个变量的函数和
我们至少可以避免使用
设置递归的赋值。

// 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
);

但我们使用 2 个变量的函数来得到 1 个变量的函数
多变的。 我们能解决这个问题吗？ 嗯，一个聪明的人，名叫
Haskell Curry 有一个巧妙的技巧，如果你有良好的高阶
那么你只需要 1 个变量的函数。 这
证明是你可以从 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 行替换为
您想要的任何其他递归函数。