12.2.1 递归的序列表达式

函数式编程中主要的控制流结构是递归。我们已经在很多例子中，写的普通函数就使用过递归，它能够解决命令式编程中的循环问题，而不需依赖可变状态。当我们想写一个简单的递归函数时，要使用 let rec 关键字，这样，就能函数以递归方式调用自身。

用于组合序列的 yield! 结构，也可以在序列表达式中执行递归调用，所以，我们同样可以使用函数编程的方法，生成序列。清单 12.4 生成所有的小于 1 百万的阶乘数，与清单 12.1 的 C# 示例一样。

清单 12.4 使用序列表达式生成序列数 (F# Interactive)

> let rec factorialsUtil(num, factorial)=    [1]

    seq { if (factorial < 1000000) then

          yield sprintf "%d! = %d" numfactorial    [2]

          let num = num + 1

          yield! factorialsUtil(num,factorial * num) };;    [3]

val factorialsUtil : int * int ->seq<string>

> let factorials = factorialsUtil(0, 1)    [4]

val factorials : seq<string> =

  seq["0! = 1"; "1! = 1"; "2! = 2"; "3! =6"; "4! = 24 ...]

清单 12.4 首先创建一个工具函数，参数为一个数字和它的阶乘[1]。当我们在后面的代码中，想要计算阶乘序列时，就调用这个函数，并给它一个最小的数字，把它的阶乘定义为起始序列[4]。这里是0，因为根据定义，0 的阶乘是 1。

整个函数体就是一个 seq 块，因此，函数将返回一个序列。在序列表达式中，我们首先检查最后的阶乘是否小于 1 百万，如果为否，就终止序列；省略了if 表达式的 else 分支，所以，不会产生任何额外的数字。如果条件为值，首先产生一个结果[2]，它表示下一个阶乘被格式化为字符串。接下来，递增这个数，并执行递归调用[3]。这将返回从下一个数字开始的阶乘序列，我们用 yield! 把它与当前的序列组合起来。

注意，因为 C# 没有对应于 yield! 的功能，所以，要将这种方法转换为 C# 是很困难的；我们必须使用foreach 循环，遍历所有元素，而这可能会导致堆栈溢出。即使能运行，由于用到大量的嵌套循环，效率也很低。在 F# 中，针对使用 yield! 尾递归进行了优化，类似于常规函数调用。这样，当序列表达式以 yield! 调用结尾，并且没有后续的代码（就像前面的这个示例），即使我们使用了多个嵌套的 yield! 调用，效率也很高。

这个示例说明，我们可以在序列表达式中，使用标准的函数式模式。我们可以在序列表达式内部使用 if 结构，以函数式风格递归地循环；F# 还可以在序列表达式内部使用可变状态（使用引用单元）和命令式循环，比如 while，但是，我们很多时候不需要它们。相反，for 循环使用相当频繁，在本章后面讨论处理序列时会看到。

数组和列表表达式

到目前为止，我们看到的序列表达式，都是括在大括号内，用 seq 标识符表示的。这种表达式生成了 seq<’a> 类型的延迟序列，对应于标准的 .NET IEnumerable<T> 类型。F# 还提供了简单的方法，用来创建不可变的 F# 列表和 .NET 数组。下面的代码段就显示了这两种集合类型：

可以发现，我们也可以把序列表达式的主体括在中括号内，就像通常构造 F# 列表时一样，在中括号后加竖线（|）构造数组。F# 把表达式主体看作普通的序列表达式，分别将结果转换为列表或数组。

当我们使用数组或列表表达式时，整个表达式是提前计算的，因为我们需要填充所有的元素。任何副作用（如打印到控制台）将会立即执行。虽然序列可以是无穷的，但是，数组和列表则不行：计算会耗尽内存。

再看一下清单 12.4，我们生成的阶乘到一个特定的限值为止。如果我们取消这个限制，会发生什么（即，删除 if 条件）呢？在通常的 F# 中，可能会无限循环，但是，在序列表达式中会发生什么呢？答案是，我们创建了一个无穷序列，它是有效的、且重要的函数式结构。

12.2.1 递归的序列表达式