Y 组合子 (Y Combinator) 可以帮助我们在 lambda 演算中实现递归函数。它的形式很简单，想要背下来也很容易。它的形式又很复杂，让你不明白它为什么长这样。

递归函数不是很好实现吗

在很多编程语言中，递归函数很好实现。比如大家喜闻乐见的 Java，要用递归的方式实现阶乘可以写成这样：

1
2
3
int fact(int n) {
  return n == 0 ? 1 : n * fact(n - 1);
}

然而，在 lambda 演算中，所有的函数都是匿名函数。因此，我们没有办法在函数fact中调用它自己。当然，我们可以通过对函数本身做一些改动来实现递归。但是这个改动可能并不那么通用，可读性也会受到影响。而 Y 组合子，则提供了一种通用的方法，可以让一个按照某种(容易 follow 的)规则实现的函数递归起来。

再一次发现 Y 组合子

Y 组合子的定义如下：

$$\lambda f.(\lambda x. f \space (x \space x)) (\lambda x. f \space (x \space x))$$

如果你把它 apply 到一个函数 g 上，你会发现 $$ (Y g) = (g \space (Y g)) $$

这也就意味着它实现了递归。只看它的定义，你可能很难理解为什么它可以做到这一点，以及发现它的人脑洞得有多大。我们今天就来一步一步的，再一次发现 Y 组合子。

把自己当作函数的参数

我们不是没法在自己的函数体内引用自己吗？那我们就把自己当作参数传进去。我们还是用阶乘举例子。首先我们用不正规的 lambda 演算定义 $f$：$$ \lambda n. n = 0\space?\space1 : n * (f \space n) $$。之所以说不正规，除了语法之外，主要是因为 $f$ 的函数体内引用了 $f$。

现在，我们给 $f$ 加一个参数的到 $f’$：

$$ f’ = \lambda s. \lambda n. n = 0\space?\space1 : n * ((s \space s) \space n)$$

这样 $ (f’ \space f’) $ 就等价于原本的 $f$ 了。

把实际的逻辑提取出来

现在，我们实现了递归。但是这种方式不够直观。我们在实际递归调用的时候，需要用 $(s \space s)$ 这种略显奇怪的形式。现在我们先做一件事，把实际的逻辑提取出来。

$$ f’ = \lambda s. \lambda n. ((\lambda g. \lambda m. m = 0\space?\space1 : m * (g \space m)) \space (s \space s)) \space n) $$

这个改动的核心在于把实际的逻辑抽出来了。有了上面这种形式，我们再把实际逻辑当作参数（我们姑且用 $fr$ 表示上面新加的 $\lambda g. \lambda m. m = 0\space?\space1 : m * (g \space m)$ ），就可以得到：

$$ f’’ = \lambda h. \lambda s. \lambda n. ((h \space (s \space s)) \space n) = \lambda h. \lambda s. h \space (s \space s)$$

$$ f’ = (f’’ fr) $$

因为 $(f’ \space f’) = f$，所以我们得到：

$$ ((f’’ \space fr) (f’’ \space fr)) = f $$

此时 $f’’$ 和我们想实现的阶乘已经是独立的了，等式左边只有 $fr$ 和阶乘有关。我们再把 $fr$ 当作参数抽取出来，等式左边就变成了：

$$ \lambda g. ((f’’ g) (f’’ g)) = \lambda g. (\lambda s. g \space (s \space s)) (\lambda s. g \space (s \space s)) = Y $$

有了这个万能的 Y 之后，我们定义阶乘的方式就变成了上面提到的 $fr$，也就是：

$$ \lambda g. \lambda m. m = 0\space?\space1 : m * (g \space m) $$

我相信任何能用 Java 实现阶乘的人，都可以轻松地写出并理解上面的代码。