使用Lambda表达式编写递归函数-拓冰建站

例如，我们想要使用Lambda表达式编写一个计算递归的fac函数，一开始我们总会设法这样做：

<span style="color:#333333"><span style="background-color:#ffffff"><span style="color:#2b91af">Func</span><<span style="color:#0000ff">int</span>, <span style="color:#0000ff">int</span>> fac = x => x <= 1 ? 1 : x * fac(x - 1);</span></span>

不过此时编译器会无情地告诉我们，fac还没有定义。于是您可能会想，这个简单，分两行写咯。于是有朋友就会给出这样的代码：

<span style="color:#333333"><span style="background-color:#ffffff"><span style="color:#2b91af">Func</span><<span style="color:#0000ff">int</span>, <span style="color:#0000ff">int</span>> fac = <span style="color:#0000ff">null</span>; fac = x => x <= 1 ? 1 : x * fac(x - 1);</span></span>

这样看起来也很“递归”，执行起来似乎也没有问题。但是，其实这并没有使用Lambda表达式构造一个递归函数，为什么呢？因为我们使用Lambda表达式构造的其实只是一个普通的匿名方法，它是这样的：

<span style="color:#333333"><span style="background-color:#ffffff">x => x <= 1 ? 1 : x * fac(x - 1);</span></span>

既然是“匿名方法”，这个构造的东西是没有名字的——因此用Lambda表达式写递归“从来不是一个很简单的事情”。那么这个Lambda表达式里的fac是什么呢？是一个“委托”。因此，这只是个“调用了一个委托”的Lambda表达式。“委托对象”和“匿名方法”是有区别的，前者是一个实际的对象，而后者只是个“定义方式”，只是“委托对象”可以成为“匿名方法”的载体而已。这个Lambda表达式构造的“委托对象”在调用时，它会去寻找fac这个引用所指向的委托对象。请注意，这里是根据“引用”去找“对象”，这意味着Lambda表达式构造的委托对象在调用时，fac可能已经不再指向当初的委托对象了。例如：

<span style="color:#333333"><span style="background-color:#ffffff"><span style="color:#2b91af">Func</span><<span style="color:#0000ff">int</span>, <span style="color:#0000ff">int</span>> fac = <span style="color:#0000ff">null</span>; fac = x => x <= 1 ? 1 : x * fac(x - 1); <span style="color:#2b91af">Console</span>.WriteLine(fac(5)); <span style="color:#008000">// 120; </span><span style="color:#2b91af">Func</span><<span style="color:#0000ff">int</span>, <span style="color:#0000ff">int</span>> facAlias = fac; fac = x => x; <span style="color:#2b91af">Console</span>.WriteLine(facAlias(5)); <span style="color:#008000">// 20</span></span></span>

第一次打印出的120是正确的结果。不过facAlias从fac那里“接过”了使用Lambda表达式构造的委托对象之后，我们让fac引用指向了新的匿名方法x => x。于是facAlias在调用时：

<span style="color:#333333"><span style="background-color:#ffffff">facAlias(5) <span style="color:#008000"><— facAlias是x => x <= 1 ? 1 : x * fac(x – 1)</span> = 5 <= 1 ? 1 : 5 * fac(5 - 1) = 5 * fac(4) <span style="color:#008000"><— 注意此时fac是x => x</span> = 5 * 4 = 20</span></span>

自然就不对了。

因此，使用Lambda表达式构造一个递归函数不是一件容易的事情。

把自己传给自己吧

可能已经有朋友知道“标准”的做法是什么样的，不过我这里还想谈一下我当时遇到这个问题时想到的一个做法。比较笨（非常符合我的特点），但是可以解决问题。

我的想法是，既然使用“Lambda表达式来构造一个递归函数”的难点是因为“我们正在构造的东西是没有名字的”，因此“我们无法调用自身”。那么，如果我们换种写法，把我们正在调用的匿名函数作为参数传给自己，那么不就可以在匿名函数的方法体中，通过调用参数来调用自身了吗？于是，原本我们构造fac方法的Lambda表达式：

<span style="color:#333333"><span style="background-color:#ffffff">x => x <= 1 ? 1 : x * fac(x - 1);</span></span>

就需要变成：

<span style="color:#333333"><span style="background-color:#ffffff">(f, x) => x <= 1 ? 1 : x * f(f, x - 1);</span></span>

请注意，这里的f参数是一个函数，它也是我们正在使用Lambda表达式定义的匿名委托（就是“(f, x) => ...”这一长串）。为了递归调用，它还必须把自身作为第一个参数传入下一层的调用中去，所以最后不是fac(x - 1)而是f(f, x - 1)。我们可以把这个匿名函数放到一个叫做selfFac的变量中去：

<span style="color:#333333"><span style="background-color:#ffffff"><span style="color:#0000ff">var</span> selfFac = (f, x) => x <= 1 ? 1 : x * f(f, x - 1);</span></span>

在第一次调用selfFac时，我们必须把它自身传递进去。于是我们可以这样来获得阶乘的结果：

<span style="color:#333333"><span style="background-color:#ffffff"><span style="color:#2b91af">Console</span>.WriteLine(selfFac(selfFac, 5)); <span style="color:#008000">// 120;</span></span></span>

但是这段代码没法编译通过，因为编译器不知道selfFac应该是什么类型的委托对象。不过根据selfFac(selfFac, 5)的调用方式，我们可以推断出，这个委托类型会接受两个参数，第一个是它自身的类型，第二个是个整型，而返回的也是个整型。于是，我们可以得出委托的签名了：

<span style="color:#333333"><span style="background-color:#ffffff"><span style="color:#0000ff">delegate int </span><span style="color:#2b91af">SelfFactorial</span>(<span style="color:#2b91af">SelfFactorial </span>selfFac, <span style="color:#0000ff">int </span>x);</span></span>

哎，但是这一点都不通用啊。没关系，我们可以写的通用一些：

<span style="color:#333333"><span style="background-color:#ffffff"><span style="color:#0000ff">delegate </span>TResult <span style="color:#2b91af">SelfApplicable</span><T, TResult>(<span style="color:#2b91af">SelfApplicable</span><T, TResult> self, T arg);</span></span>

这样，我们便可以定义selfFac，甚至于selfFib（菲波纳契数列）：

<span style="color:#333333"><span style="background-color:#ffffff"><span style="color:#2b91af">SelfApplicable</span><<span style="color:#0000ff">int</span>, <span style="color:#0000ff">int</span>> selfFib = (f, x) => x <= 1 ? 1 : f(f, x - 1) + f(f, x - 2); <span style="color:#2b91af">Console</span>.WriteLine(selfFib(selfFib, 5)); <span style="color:#008000">// 8</span></span></span>

但是，这还不是我们所需要的递归函数啊。没错，我们需要的是传入一个x就可以得到结果的函数，这种每次还需要把自己传进去的东西算什么？不过这个倒也容易，在selfXxx的基础上再前进一步就可以了：

<span style="color:#333333"><span style="background-color:#ffffff"><span style="color:#2b91af">SelfApplicable</span><<span style="color:#0000ff">int</span>, <span style="color:#0000ff">int</span>> selfFac = (f, x) => x <= 1 ? 1 : x * f(f, x - 1); <span style="color:#2b91af">Func</span><<span style="color:#0000ff">int</span>, <span style="color:#0000ff">int</span>> fac = x => selfFac(selfFac, x); <span style="color:#2b91af">SelfApplicable</span><<span style="color:#0000ff">int</span>, <span style="color:#0000ff">int</span>> selfFib = (f, x) => x <= 1 ? 1 : f(f, x - 1) + f(f, x - 2); <span style="color:#2b91af">Func</span><<span style="color:#0000ff">int</span>, <span style="color:#0000ff">int</span>> fib = x => selfFib(selfFib, x);</span></span>

为此，我们甚至可以总结出一个辅助方法：

<span style="color:#333333"><span style="background-color:#ffffff"><span style="color:#0000ff">static </span><span style="color:#2b91af">Func</span><T, TResult> Make<T, TResult>(<span style="color:#2b91af">SelfApplicable</span><T, TResult> self) { <span style="color:#0000ff">return </span>x => self(self, x); }</span></span>

于是乎：

<span style="color:#333333"><span style="background-color:#ffffff"><span style="color:#0000ff">var </span>fac = Make<<span style="color:#0000ff">int</span>, <span style="color:#0000ff">int</span>>((f, x) => x <= 1 ? 1 : x * f(f, x - 1)); <span style="color:#0000ff">var </span>fib = Make<<span style="color:#0000ff">int</span>, <span style="color:#0000ff">int</span>>((f, x) => x <= 1 ? 1 : f(f, x - 1) + f(f, x - 2));</span></span>

这样我们便使用Lambda表达式定义了递归函数。当然，需要两个参数的递归函数定义方式也比较类似。首先是SelfApplicable委托类型和对应的辅助方法：

<span style="color:#333333"><span style="background-color:#ffffff"><span style="color:#008000">// 委托类型 </span><span style="color:#0000ff">delegate </span>TResult <span style="color:#2b91af">SelfApplicable</span><T1, T2, TResult>(<span style="color:#2b91af">SelfApplicable</span><T1, T2, TResult> self, T1 arg1, T2 arg2); <span style="color:#008000">// 辅助方法 </span><span style="color:#0000ff">static </span><span style="color:#2b91af">Func</span><T1, T2, TResult> Make<T1, T2, TResult>(<span style="color:#2b91af">SelfApplicable</span><T1, T2, TResult> self) { <span style="color:#0000ff">return </span>(x, y) => self(self, x, y); }</span></span>

于是使用“辗转相除法”计算最大公约数的gcd函数便是：

<span style="color:#333333"><span style="background-color:#ffffff"><span style="color:#0000ff">var </span>gcd = Make<<span style="color:#0000ff">int</span>, <span style="color:#0000ff">int</span>, <span style="color:#0000ff">int</span>>((f, x, y) => y == 0 ? x : f(f, y, x % y)); <span style="color:#2b91af">Console</span>.WriteLine(gcd(20, 36)); <span style="color:#008000">// 4</span></span></span>

这也是我目前凭“个人能力”能够走出的最远距离了。

不动点组合子

但是装配脑袋很早给了我们更好的解决方法：

<span style="color:#333333"><span style="background-color:#ffffff"><span style="color:#0000ff">static </span><span style="color:#2b91af">Func</span><T, TResult> Fix<T, TResult>(<span style="color:#2b91af">Func</span><<span style="color:#2b91af">Func</span><T, TResult>, <span style="color:#2b91af">Func</span><T, TResult>> f) { <span style="color:#0000ff">return </span>x => f(Fix(f))(x); } <span style="color:#0000ff">static </span><span style="color:#2b91af">Func</span><T1, T2, TResult> Fix<T1, T2, TResult>(<span style="color:#2b91af">Func</span><<span style="color:#2b91af">Func</span><T1, T2, TResult>, <span style="color:#2b91af">Func</span><T1, T2, TResult>> f) { <span style="color:#0000ff">return </span>(x, y) => f(Fix(f))(x, y); }</span></span>

Fix求出的是函数f的不动点，它就是我们所需要的递归函数：

<span style="color:#333333"><span style="background-color:#ffffff"><span style="color:#0000ff">var </span>fac = Fix<<span style="color:#0000ff">int</span>, <span style="color:#0000ff">int</span>>(f => x => x <= 1 ? 1 : x * f(x - 1)); <span style="color:#0000ff">var </span>fib = Fix<<span style="color:#0000ff">int</span>, <span style="color:#0000ff">int</span>>(f => x => x <= 1 ? 1 : f(x - 1) + f(x - 2)); <span style="color:#0000ff">var </span>gcd = Fix<<span style="color:#0000ff">int</span>, <span style="color:#0000ff">int</span>, <span style="color:#0000ff">int</span>>(f => (x, y) => y == 0 ? x : f(y, x % y));</span></span>

用脑袋的话来说，Fix方法应该被视为是内置方法。您比较Fix方法内部和之前的Make方法内部的写法，就能够意识到两种做法之间的差距了。

由于我的脑袋不如装配脑袋的脑袋装配的那么好，即使看来一些推导过程之后还是无法做到100%的理解，我还需要的内容。希望在以后的某一天，我可以把这部分内容融会贯通地理解下来，并且可以详细地解释给大家听。在这之前，我还是听脑袋的话，把Fix强行记在脑袋里吧。

最后，希望大家多多参与一些如“函数式链表快速排序”这样的趣味编程——不过，千万不要学脑袋这样做：

<span style="color:#333333"><span style="background-color:#ffffff"><span style="color:#0000ff">var </span>qsort = Fix<<span style="color:#2b91af">IEnumerable</span><<span style="color:#0000ff">int</span>>, <span style="color:#2b91af">IEnumerable</span><<span style="color:#0000ff">int</span>>>(f => l => l.Any() ? f(l.Skip(1).Where(e => e < l.First())).Concat(<span style="color:#2b91af">Enumerable</span>.Repeat(l.First(), 1)).Concat(f(l.Skip(1).Where(e => e >= l.First()))) : <span style="color:#2b91af">Enumerable</span>.Empty<<span style="color:#0000ff">int</span>>());</span></span>

当然，偶尔玩玩是有益无害的。