使用Lambda表达式编写递归函数

例如我们想要使用Lambda表达式编写一个计算递归的fac函数一开始我们总会设法这样做span stylecolor:#333333span stylebackground-color:#ffffffspan stylecolor:#2b91afFunc/spanspan stylecolor:#0000ffint/span, span stylecolor:#0000ffint/span fac x x 1 ? 1 : x * fac(x - 1);/span/span不过此时编译器会无情地告诉我们fac还没有定义。于是您可能会想这个简单分两行写咯。于是有朋友就会给出这样的代码span stylecolor:#333333span stylebackground-color:#ffffffspan stylecolor:#2b91afFunc/spanspan stylecolor:#0000ffint/span, span stylecolor:#0000ffint/span fac span stylecolor:#0000ffnull/span; fac x x 1 ? 1 : x * fac(x - 1);/span/span这样看起来也很“递归”执行起来似乎也没有问题。但是其实这并没有使用Lambda表达式构造一个递归函数为什么呢因为我们使用Lambda表达式构造的其实只是一个普通的匿名方法它是这样的span stylecolor:#333333span stylebackground-color:#ffffffx x 1 ? 1 : x * fac(x - 1);/span/span既然是“匿名方法”这个构造的东西是没有名字的——因此用Lambda表达式写递归“从来不是一个很简单的事情”。那么这个Lambda表达式里的fac是什么呢是一个“委托”。因此这只是个“调用了一个委托”的Lambda表达式。“委托对象”和“匿名方法”是有区别的前者是一个实际的对象而后者只是个“定义方式”只是“委托对象”可以成为“匿名方法”的载体而已。这个Lambda表达式构造的“委托对象”在调用时它会去寻找fac这个引用所指向的委托对象。请注意这里是根据“引用”去找“对象”这意味着Lambda表达式构造的委托对象在调用时fac可能已经不再指向当初的委托对象了。例如span stylecolor:#333333span stylebackground-color:#ffffffspan stylecolor:#2b91afFunc/spanspan stylecolor:#0000ffint/span, span stylecolor:#0000ffint/span fac span stylecolor:#0000ffnull/span; fac x x 1 ? 1 : x * fac(x - 1); span stylecolor:#2b91afConsole/span.WriteLine(fac(5)); span stylecolor:#008000// 120; /spanspan stylecolor:#2b91afFunc/spanspan stylecolor:#0000ffint/span, span stylecolor:#0000ffint/span facAlias fac; fac x x; span stylecolor:#2b91afConsole/span.WriteLine(facAlias(5)); span stylecolor:#008000// 20/span/span/span第一次打印出的120是正确的结果。不过facAlias从fac那里“接过”了使用Lambda表达式构造的委托对象之后我们让fac引用指向了新的匿名方法x x。于是facAlias在调用时span stylecolor:#333333span stylebackground-color:#fffffffacAlias(5) span stylecolor:#008000— facAlias是x x 1 ? 1 : x * fac(x – 1)/span 5 1 ? 1 : 5 * fac(5 - 1) 5 * fac(4) span stylecolor:#008000— 注意此时fac是x x/span 5 * 4 20/span/span自然就不对了。因此使用Lambda表达式构造一个递归函数不是一件容易的事情。把自己传给自己吧可能已经有朋友知道“标准”的做法是什么样的不过我这里还想谈一下我当时遇到这个问题时想到的一个做法。比较笨非常符合我的特点但是可以解决问题。我的想法是既然使用“Lambda表达式来构造一个递归函数”的难点是因为“我们正在构造的东西是没有名字的”因此“我们无法调用自身”。那么如果我们换种写法把我们正在调用的匿名函数作为参数传给自己那么不就可以在匿名函数的方法体中通过调用参数来调用自身了吗于是原本我们构造fac方法的Lambda表达式span stylecolor:#333333span stylebackground-color:#ffffffx x 1 ? 1 : x * fac(x - 1);/span/span就需要变成span stylecolor:#333333span stylebackground-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 stylecolor:#333333span stylebackground-color:#ffffffspan stylecolor:#0000ffvar/span selfFac (f, x) x 1 ? 1 : x * f(f, x - 1);/span/span在第一次调用selfFac时我们必须把它自身传递进去。于是我们可以这样来获得阶乘的结果span stylecolor:#333333span stylebackground-color:#ffffffspan stylecolor:#2b91afConsole/span.WriteLine(selfFac(selfFac, 5)); span stylecolor:#008000// 120;/span/span/span但是这段代码没法编译通过因为编译器不知道selfFac应该是什么类型的委托对象。不过根据selfFac(selfFac, 5)的调用方式我们可以推断出这个委托类型会接受两个参数第一个是它自身的类型第二个是个整型而返回的也是个整型。于是我们可以得出委托的签名了span stylecolor:#333333span stylebackground-color:#ffffffspan stylecolor:#0000ffdelegate int /spanspan stylecolor:#2b91afSelfFactorial/span(span stylecolor:#2b91afSelfFactorial /spanselfFac, span stylecolor:#0000ffint /spanx);/span/span哎但是这一点都不通用啊。没关系我们可以写的通用一些span stylecolor:#333333span stylebackground-color:#ffffffspan stylecolor:#0000ffdelegate /spanTResult span stylecolor:#2b91afSelfApplicable/spanT, TResult(span stylecolor:#2b91afSelfApplicable/spanT, TResult self, T arg);/span/span这样我们便可以定义selfFac甚至于selfFib菲波纳契数列span stylecolor:#333333span stylebackground-color:#ffffffspan stylecolor:#2b91afSelfApplicable/spanspan stylecolor:#0000ffint/span, span stylecolor:#0000ffint/span selfFib (f, x) x 1 ? 1 : f(f, x - 1) f(f, x - 2); span stylecolor:#2b91afConsole/span.WriteLine(selfFib(selfFib, 5)); span stylecolor:#008000// 8/span/span/span但是这还不是我们所需要的递归函数啊。没错我们需要的是传入一个x就可以得到结果的函数这种每次还需要把自己传进去的东西算什么不过这个倒也容易在selfXxx的基础上再前进一步就可以了span stylecolor:#333333span stylebackground-color:#ffffffspan stylecolor:#2b91afSelfApplicable/spanspan stylecolor:#0000ffint/span, span stylecolor:#0000ffint/span selfFac (f, x) x 1 ? 1 : x * f(f, x - 1); span stylecolor:#2b91afFunc/spanspan stylecolor:#0000ffint/span, span stylecolor:#0000ffint/span fac x selfFac(selfFac, x); span stylecolor:#2b91afSelfApplicable/spanspan stylecolor:#0000ffint/span, span stylecolor:#0000ffint/span selfFib (f, x) x 1 ? 1 : f(f, x - 1) f(f, x - 2); span stylecolor:#2b91afFunc/spanspan stylecolor:#0000ffint/span, span stylecolor:#0000ffint/span fib x selfFib(selfFib, x);/span/span为此我们甚至可以总结出一个辅助方法span stylecolor:#333333span stylebackground-color:#ffffffspan stylecolor:#0000ffstatic /spanspan stylecolor:#2b91afFunc/spanT, TResult MakeT, TResult(span stylecolor:#2b91afSelfApplicable/spanT, TResult self) { span stylecolor:#0000ffreturn /spanx self(self, x); }/span/span于是乎span stylecolor:#333333span stylebackground-color:#ffffffspan stylecolor:#0000ffvar /spanfac Makespan stylecolor:#0000ffint/span, span stylecolor:#0000ffint/span((f, x) x 1 ? 1 : x * f(f, x - 1)); span stylecolor:#0000ffvar /spanfib Makespan stylecolor:#0000ffint/span, span stylecolor:#0000ffint/span((f, x) x 1 ? 1 : f(f, x - 1) f(f, x - 2));/span/span这样我们便使用Lambda表达式定义了递归函数。当然需要两个参数的递归函数定义方式也比较类似。首先是SelfApplicable委托类型和对应的辅助方法span stylecolor:#333333span stylebackground-color:#ffffffspan stylecolor:#008000// 委托类型 /spanspan stylecolor:#0000ffdelegate /spanTResult span stylecolor:#2b91afSelfApplicable/spanT1, T2, TResult(span stylecolor:#2b91afSelfApplicable/spanT1, T2, TResult self, T1 arg1, T2 arg2); span stylecolor:#008000// 辅助方法 /spanspan stylecolor:#0000ffstatic /spanspan stylecolor:#2b91afFunc/spanT1, T2, TResult MakeT1, T2, TResult(span stylecolor:#2b91afSelfApplicable/spanT1, T2, TResult self) { span stylecolor:#0000ffreturn /span(x, y) self(self, x, y); }/span/span于是使用“辗转相除法”计算最大公约数的gcd函数便是span stylecolor:#333333span stylebackground-color:#ffffffspan stylecolor:#0000ffvar /spangcd Makespan stylecolor:#0000ffint/span, span stylecolor:#0000ffint/span, span stylecolor:#0000ffint/span((f, x, y) y 0 ? x : f(f, y, x % y)); span stylecolor:#2b91afConsole/span.WriteLine(gcd(20, 36)); span stylecolor:#008000// 4/span/span/span这也是我目前凭“个人能力”能够走出的最远距离了。不动点组合子但是装配脑袋很早给了我们更好的解决方法span stylecolor:#333333span stylebackground-color:#ffffffspan stylecolor:#0000ffstatic /spanspan stylecolor:#2b91afFunc/spanT, TResult FixT, TResult(span stylecolor:#2b91afFunc/spanspan stylecolor:#2b91afFunc/spanT, TResult, span stylecolor:#2b91afFunc/spanT, TResult f) { span stylecolor:#0000ffreturn /spanx f(Fix(f))(x); } span stylecolor:#0000ffstatic /spanspan stylecolor:#2b91afFunc/spanT1, T2, TResult FixT1, T2, TResult(span stylecolor:#2b91afFunc/spanspan stylecolor:#2b91afFunc/spanT1, T2, TResult, span stylecolor:#2b91afFunc/spanT1, T2, TResult f) { span stylecolor:#0000ffreturn /span(x, y) f(Fix(f))(x, y); }/span/spanFix求出的是函数f的不动点它就是我们所需要的递归函数span stylecolor:#333333span stylebackground-color:#ffffffspan stylecolor:#0000ffvar /spanfac Fixspan stylecolor:#0000ffint/span, span stylecolor:#0000ffint/span(f x x 1 ? 1 : x * f(x - 1)); span stylecolor:#0000ffvar /spanfib Fixspan stylecolor:#0000ffint/span, span stylecolor:#0000ffint/span(f x x 1 ? 1 : f(x - 1) f(x - 2)); span stylecolor:#0000ffvar /spangcd Fixspan stylecolor:#0000ffint/span, span stylecolor:#0000ffint/span, span stylecolor:#0000ffint/span(f (x, y) y 0 ? x : f(y, x % y));/span/span用脑袋的话来说Fix方法应该被视为是内置方法。您比较Fix方法内部和之前的Make方法内部的写法就能够意识到两种做法之间的差距了。由于我的脑袋不如装配脑袋的脑袋装配的那么好即使看来一些推导过程之后还是无法做到100%的理解我还需要的内容。希望在以后的某一天我可以把这部分内容融会贯通地理解下来并且可以详细地解释给大家听。在这之前我还是听脑袋的话把Fix强行记在脑袋里吧。最后希望大家多多参与一些如“函数式链表快速排序”这样的趣味编程——不过千万不要学脑袋这样做span stylecolor:#333333span stylebackground-color:#ffffffspan stylecolor:#0000ffvar /spanqsort Fixspan stylecolor:#2b91afIEnumerable/spanspan stylecolor:#0000ffint/span, span stylecolor:#2b91afIEnumerable/spanspan stylecolor:#0000ffint/span(f l l.Any() ? f(l.Skip(1).Where(e e l.First())).Concat(span stylecolor:#2b91afEnumerable/span.Repeat(l.First(), 1)).Concat(f(l.Skip(1).Where(e e l.First()))) : span stylecolor:#2b91afEnumerable/span.Emptyspan stylecolor:#0000ffint/span());/span/span当然偶尔玩玩是有益无害的。分类 03. 语言编程标签 Lambda表达式 , 匿名方法 , 递归 , 不动点组合子