[翻译]轻松7步，导出Y结合子

本文译自 “Deriving the Y Combinator in 7 Easy Steps“，

原文链接：http://igstan.ro/posts/2010-12-01-deriving-the-y-combinator-in-7-easy-steps.html

在没有原生递归支持的语言中，Y结合子（Y Combinator）是一种实现递归的方式（事实上，它更常被作为一种锻炼程序思维的方式）。要实现Y结合子，要求这种语言支持匿名函数。

此处，我选择JavaScript来推导Y结合子，从递归阶乘函数的定义开始，一步一步进行变换。

最初的实现，使用JavaScript内建的递归机制。

1 2 3 4	var fact = function (n) { if (n < 2) return 1; return n * fact(n - 1); };

获得递归的最简单方法是什么？我们可以定义一个函数，它接受它自身作为参数，并且用这个参数作为参数，调用这个参数。当然，这是一个无限循环，会导致栈溢出。

1 2 3 4 5	(function (f) { f(f); })(function (f) { f(f); });

我们的阶乘函数套用上面的模板，再做点改动，阶乘函数接受一个我们还不知道的参数，所以我们要的是返回一个接受该参数的函数。然后这个函数可以被用于计算阶乘。同时，这可以让我们的阶乘函数不会无限循环下去。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17	var fact = (function (f) { return function (n) { // 终止条件 if (n < 2) return 1; //因为f返回一个函数，所以这有一个双重调用。 return n * f(f)(n - 1); }; })(function (f) { return function (n) { // 终止条件 if (n < 2) return 1; // 因为f返回一个函数，所以这有一个双重调用。 return n * f(f)(n - 1); }; });

此时，我们的代码有一些糟糕的重复，让我们把放进一个名叫recur的辅助函数里。

1 2 3 4 5 6 7 8 9 10 11 12	var recur = function (f) { return f(f); }; var fact = recur(function (f) { return function (n) { if (n < 2) return 1; // 因为f返回一个函数，所以这有一个双重调用。 return n * f(f)(n - 1); }; });

上面这个版本的问题是，它有两重调用（指的是f(f)(n-1)）。我们想去除它，让我们的函数跟接近于递归版本。怎么做呢？

我们可以使用一个辅助函数，它接受一个数值参数，进行两重调用。这个trick通过把辅助函数放在可见f的作用域里，所以g可以调用f。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16	var recur = function (f) { return f(f); }; var fact = recur(function (f) { var g = function (n) { return f(f)(n); }; return function (n) { if (n < 2) return 1; // 没有双重调用了，函数g接受一个数值参数。 return n * g(n - 1); }; });

以上版本工作良好，但是它的定义太杂乱了。我们可以把它再清理为一个辅助函数，把阶乘定义尽可能分离出来。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20	var recur = function (f) { return f(f); }; var wrap = function (h) { return recur(function (f) { var g = function (n) { return f(f)(n); }; return h(g); }); }; var fact = wrap(function (g) { return function (n) { if (n < 2) return 1; return n * g(n - 1); }; });

g只调用了一次，让我们把g内联进wrap里。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18	var recur = function (f) { return f(f); }; var wrap = function (h) { return recur(function (f) { return h(function (n) { return f(f)(n); }); }); }; var fact = wrap(function (g) { return function (n) { if (n < 2) return 1; return n * g(n - 1); }; });

现在，如果我们把recur也内联进wrap里，我们就得到了著名的Y结合子！

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16	var Y = function (h) { return (function (f) { return f(f); })(function (f) { return h(function (n) { return f(f)(n); }); }); }; var fact = Y(function (g) { return function (n) { if (n < 2) return 1; return n * g(n - 1); }; });

玩的开心！