如何使用Lambda表达式编写递归

这篇文章主要介绍“如何使用Lambda表达式编写递归”，在日常操作中，相信很多人在如何使用Lambda表达式编写递归问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”如何使用Lambda表达式编写递归”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

递归参数及返回值类型假定

对于常见的递归函数，如：阶乘、斐波那契数列求值，我们先作如下假定：

参数为 int 类型（Int32）；

返回值为 long 类型（Int64）。

基于假推断各类型

FIX g 类型

根据上篇文章中的描述：

FIX g = λn. (ISZERO n) 1 (MULT n ((FIX g) (PRED n)))FIX g 55 = 5 * (4 * (3 * (2 * (1 * 1))) = 120

FIX g 返回的是我们需要的递归函数，这个递归函数

·接收一个 int 参数（上面假定第 1 条）值为 5

·返回一个 long 型数值（上面假定第 2 条）120。

因此，确定出 FIX g 的类型可表示为 Func<int, long>。

同时也能看出 n 是递归函数的参数，n 类型为 int。

g 类型

阶乘单步函数如下：

g = λf. λn. (ISZERO n) 1 (MULT n (f (PRED n)))

c# 中可表达为：g => f => n => n == 0 ? 1 : n * f(n &ndash; 1)

先来推断 f 的类型：

&middot;f 的参数：f 接收 n &ndash; 1 作为参数，因此，f 参数的类型和 n &ndash; 1 类型相同，即 n 的类型：int；

&middot;f 的返回值：为 0 时返回 1，否则返回 n * f(n-1)，f 的返回值类型也就是整个递归函数的返回值类型，即 long。

可确定 f 类型为 Func<int, long>。

n => n == 0 ? 1 : n * f(n &ndash; 1) 是传入一个 int 返回一个 long，其类型 Func<int, long>。

先来变换下 g 的表示形式：

var g = (Func<int, long> f) => {      Func<int, long> t =           n => n == 0 ? 1 : n * f(n - 1);      return t;  };  // 示意代码

从上面这段代码可以清楚到看出 g 接收一个 Func<int, long> 类型的参数 f，返回一个类型为 Func<int, long> 的委托，可得出：

g 的类型为 Func<Func<int, long>, Func<int, long>>

FIX 类型

FIX g 可写作 FIX(g)，可以看出： FIX g 的类型 == FIX(g) 的类型 == FIX 返回值的类型。前面得知 FIX g 类型为 Func<int, long>，也就可推出 FIX 返回值类型为 Func<int, long>。

FIX 接受 g 作为参数，FIX 的参数类型也就是 g 的类型，可知 FIX 参数类型为 Func<Func<int, long>, Func<int, long>>。

由此得出 FIX 的类型为：Func<Func<Func<int, long>, Func<int, long>>, Func<int, long>>。

（估计这是多数开发人员见过的最复杂的泛型了。后面还在更复杂的吆！）

小结

通用类型

基于以上部分的推演和小结，我们可以归纳出通用类型：

基于本文推断出的类型，不动点组合子转换为 c# 代码了不容易多了。

到此，关于“如何使用Lambda表达式编写递归”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注编程网网站，小编会继续努力为大家带来更多实用的文章！