注：阅读本文可能需要一定 LISP或 Racket的基础知识，若没有相关基础则可查阅 Racket官方文档 来进行对照学习。
概述
在Rakect中存在一个特性叫“Y Combinator”， 它可以使你在不使用 letrec 或正常使用 define 来定义一个过程（procedure）的情况下以匿名过程 （anonymous procedures）的方式写出递归函数。我们可以先从介绍它的使用方式作为开头。例如，在Racket中，我们可以使用Y Combinator来书写一个求整数n阶乘的过程如下：
(def Fact
(Y (λ (fact)
(λ (n)
(if (zero? n)
1
(* n (fact (- n 1))))))))
由上面的例子我们可以看出，对于一个过程 f， Y Combinator的使用方式是 (Y f) ， 且由于我们使用匿名过程的原因，我们需要将一个我们想使用的过程名字作为 f 的参数， 然后将对应问题的输入作为 f 所返回的过程的参数。在求阶乘的问题里，我们选用整数 n 作为我们返回的过程的参数。
原理
那么， 接下来的问题是，为什么我们可以这么做？Y Combinator的运作原理又是什么？简单来说，Y Combinator的理论来自于Lambda Calculus中的Eta-Reduction，其相关内容在这里不做讲述。我们主要从Y Combinator的实现来解决该疑问。下面是Y Combinator的具体实现：
(define Y
(λ (f)
((λ (g) (f (g g)))
(λ (g) (f (g g))))))这段代码可能阅读与理解起来有些困难，但我们可以把它进行一些简化之后再进行分析。我们首先添加如下的定义：
(define p (λ (g) (f (g g))))利用上述定义，我们就可以讲Y Combinator的实现简化为如下形式：
(define Y (λ (f) (p p)))通过简化后的代码我们不难看出，Y 是一个过程，且这个过程返回的是将上文定义的过程p作为参数传入自己本身后得出的结果，即 (p p)。接下来，我们可以尝试给过程 Y 传入一个过程 k 作为参数，看一看会发生什么。
(Y k) = (λ (g) (k (g g)))
(λ (g) (k (g g)))
= (k (λ (g) (k (g g)))
(λ (g) (k (g g))))
= (k (Y k))由此，我们不难得出，对于任意过程 f，(Y f) = (f (Y f))。根据这点，我们也可以知晓Y Combinator就是利用了 (Y f) = (f (Y f)) 的特性来实现递归。
Z/Z* Combinator
在Racket中Y Combinator的确很巧妙，但是在Scheme中，使用Y Combinator则会导致Scheme先解析 (Y f) 而陷入死循环。于是，我们便有了Z Combinator作为契合Scheme特点的Y Combinator。我在这里放出Z Combinator的实现，大家可以依照上文的分析来推导出Z Combinator的原理。
(define Z
(λ (f)
((λ (g) (f (λ (v) ((g g) v)))
(λ (g) (f (λ (v) ((g g) v))))))在Z Combinator中， v是作为问题要求的输入存在的。
除了Z Combinator，我们还有针对不确定数量参数的过程的Z* Combinator，由于它和Z Combinator除了构造上有所不同其他方面并无太大差别，所以在此只给出实现代码，具体原理与特性可以依照上一节的内容进行推理。
(define Z*
(λ (f)
((λ (g) (f (λ args (apply (g g) args)))
(λ (g) (f (λ args (apply (g g) args))))))References
- 3.11 Theory in Racket Official Document.
- Sildes of CS275 at Oberlin College.
