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

其实这从来不是一个很简单的事情，虽然有些朋友认为这很简单。
伪递归

我的意思是，某些看上去像递归的做法，事实上并非是递归，所以我把它叫做是“伪”递归。
例如，我们想要使用Lambda表达式编写一个计算递归的fac函数，一开始我们总会设法这样做：

1. Func<int, int> fac = x => x <= 1 ? 1 : x * fac(x - 1);

复制代码

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

1. Func<int, int> fac = null;
2. fac = x => x <= 1 ? 1 : x * fac(x - 1);

复制代码

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

1. x => x <= 1 ? 1 : x * fac(x - 1);

复制代码

于是乎：

1. Func<int, int> fac = null;
2. fac = x => x <= 1 ? 1 : x * fac(x - 1);
3. Console.WriteLine(fac(5)); // 120;
5. Func<int, int> facAlias = fac;
6. fac = x => x;
7. Console.WriteLine(facAlias(5)); // 20

复制代码

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

1. facAlias(5)     <— facAlias是x => x <= 1 ? 1 : x * fac(x – 1)
2. = 5 <= 1 ? 1 : 5 * fac(5 - 1)
3. = 5 * fac(4)    <— 注意此时fac是x => x
4. = 5 * 4
5. = 20

复制代码

这也是我目前凭“个人能力”能够走出的最远距离了。
不动点组合子

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

1. x => x <= 1 ? 1 : x * fac(x - 1);

复制代码

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

1. (f, x) => x <= 1 ? 1 : x * f(f, x - 1);

复制代码

用脑袋的话来说，Fix方法应该被视为是内置方法。您比较Fix方法内部和之前的Make方法内部的写法，就能够意识到两种做法之间的差距了。
由于我的脑袋不如装配脑袋的脑袋装配的那么好，即使看来一些推导过程之后还是无法做到100%的理解，我还需要阅读更多的内容。希望在以后的某一天，我可以把这部分内容融会贯通地理解下来，并且可以详细地解释给大家听。在这之前，我还是听脑袋的话，把Fix强行记在脑袋里吧。
最后，希望大家多多参与一些如“函数式链表快速排序”这样的趣味编程——不过，千万不要学脑袋这样做：

1. var selfFac = (f, x) => x <= 1 ? 1 : x * f(f, x - 1);

复制代码

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

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！