本文译自 “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结合子，从递归阶乘函数的定义开始，一步一步进行变换。
Step 1
最初的实现，使用JavaScript内建的递归机制。
1
2
3
4
|
var fact = function (n) {
if (n < 2) return 1;
return n * fact(n - 1);
};
|
Step 2
获得递归的最简单方法是什么？我们可以定义一个函数，它接受它自身作为参数，并且用这个参数作为参数，调用这个参数。当然，这是一个无限循环，会导致栈溢出。
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);
};
});
|
Step 3
此时，我们的代码有一些糟糕的重复，让我们把放进一个名叫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);
};
});
|
Step 4
上面这个版本的问题是，它有两重调用（指的是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);
};
});
|
Step 5
以上版本工作良好，但是它的定义太杂乱了。我们可以把它再清理为一个辅助函数，把阶乘定义尽可能分离出来。
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);
};
});
|
Step 6
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);
};
});
|
Step 7
现在，如果我们把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);
};
});
|
The End
玩的开心！