1
Func<int, int> fact = x => x <= 1 ? 1 : x * fact(x - 1);
不过这种写法也有问题，老赵说得比较清楚，我就不在赘述了，请查看《
使用Lambda表达式编写递归函数
》一文中
伪递归
部分。
那么如何解决 lambda 表达式构建递归函数的问题呢？根据函数式编程理论，我们可以使用
不动点组合子
。
在学习
不动点组合子
之前，需要先了解更基础
λ 演算
。
λ 演算的基础请大家参考维基百科：
http://zh.wikipedia.org/wiki/Lambda_演算
http://en.wikipedia.org/wiki/Lambda_calculus
非形式化的描述
请确保你已经理解了文中几个表达式的等价关系：
定义匿名的递归函数
不动点组合子允许定义匿名的递归函数，具体来说是将一个非递归的
单步函数
（只执行递归中的一步，a single step of this recursion，使用 g 表示）转换为递归函数。
如下是阶乘的
单步函数
定义：
根据此描述，可知 λ 演算中函数只有一个参数，这个
参数是一个函数，而不是一个值
。而对于我们常见的递归（阶乘、斐波那契数列求值），参数都是值（自然数）。两者是不匹配的。
为了适当传值调用，需要将不动点组合子
η-展开：
简单而言
η-变换
是说 λx. f x 和 f 可以互相转换。从 f 这种简单形式
η-变换
为 λx. f x 复杂形式，称为
η-展开
。
对于 Y 组合子，通常是将其中的 (x x) η-展开为 λy. x x y，由此得出传值调用版本的 Y组合子（也称为 Z 组合子）：
// (λx. λy. λz. x + y + z) 1 → λy. λz. 1 + y + z
Func<
int
, Func<
int
,
int
>> g = f(1);
// (λy. λz. 1 + y + z) 2 → λz. 1 + 2 + z → λz. 3 + z
Func<
int
,
int
> h = g(2);
// (λz. 3 + z) 3 → 3 + 3 → 6
var
result2 = h(3);
// 结果为 6
每 5 行，向 f 传入一个常量 1，返回一个新的方法 g；再经过第 7 行，向 g 传入常量 2，再次返回一个新方法 h。
方法 h 只能接受一个参数，最后得出 h(3) = 6。
为什么不是 (x, y, z) => x + y + z？
也许你会有疑问，不就是 x、y、z 三个整数加起来嘛，为什么搞这么复杂，像下面这样不是更简单吗？
运用上的的规律，可以写出 lambda 表达式：x => n => g((x(x))(n)
对于复杂点的如：λx. f ( λv. (x x) v)，这条规律就不适用了。文后续部分会通过演算绕开这种复杂的转换，不对此进行讨论。
理解本文中的泛型和 lambda 表达式
对于上一部分使用的泛型和 lambda 表达式，尤其是下面这行代码，你需要花点时间去理理思路（因为后续章节中泛型要远比此复杂）：
本文简单阐述了 lambda 构建递归函数的问题，粗略提及 λ 演算及不动点组合子的知识，并总结了下 λ 演算表达式与 c# lambda 表达式的对应关系。
下一篇文章
将推断 FIX、g 的参数及返回值类型。
-------------------
思想火花，照亮世界
|
