10.2.1 用尾递归避免栈溢出（续!）

[

na?ve

不像是英语，不知道什么意思。

]

第六章中的列表处理函数并不是尾递归。如果我们传递很大的列表，就会因栈溢出而失败。我们将用尾递归重写两个函数（map 和 filter），将改正这个问题。为了对照，在清单 10.8 中包括了原来的实现。为了避免名字冲突，已经改名为 mapN 和 filterN。

清单10.8 na?ve 列表处理函数 (F#)

// Na?ve ‘map‘ implementation 

let rec mapN f list = 

  match list with 

  | [] –> [] 

  | x::xs -> let xs = (mapN fxs)     [1]

                f(x) :: xs                   [2]

// Na?ve ‘filter‘ implementation

let rec filterN f list =

  match list with

  | [] –> []

  | x::xs -> let xs = (filterN fxs)    [1]

                if f(x) then x::xs else xs       [2]

两个函数都包含一个递归调用[2]，但不是尾递归；递归调用每个分支都跟关一个额外的操作[2]。一般的模式是，函数首先把列表分解成头和尾；然后，递归处理尾，用头执行一些动作。更确切地说，mapN 应用 f 函数到头中的值，filterN 决定头中的值是否应包括在结果列表中。最后的操作是把新的头中的值（或者筛选分支中没有值）追加到递归处理的尾中，且在递归调用后必须处理。

要把这些函数变成尾递归，使用前面曾看到的、同样的累加器参数方法。在遍历列表时，收集元素（筛选或映射），并把它们存放在累加器中；一旦到达终点，就可以返回已经收集到的元素。清单 10.9 显示了映射和筛选的尾递归实现。

清单10.9 尾递归列表处理函数 (F#)

// Tail-recursive ‘map‘implementation 

let map f list = 

  let rec map‘ f list acc = 

    match list with 

    | [] ->List.rev(acc)          [1]

    | x::xs -> let acc =f(x)::acc       [2]

                   map‘f xs acc        [3]

    map‘ f list []

// Tail-recursive ‘filter‘implementation 

let filter f list = 

  let rec filter‘ f list acc= 

    match list with 

    | [] ->List.rev(acc)      [1]

    | x::xs -> let acc =if f(x) then x::acc else acc    [2]

                   filter‘f xs acc    [3]

    filter‘ f list []

像通常实现尾递归函数一样，这两个函数都包含本地的工具函数，有一个额外的累加器参数。这一次，我们在函数名上增加了一个单引号（‘），起初看起来有点怪。F# 把单引号当作标准的字符，可以在名称中使用，因此，也没有什么神奇的事情。

我们首先看一下终止递归的分支[1]，我们说是仅返回收集到的元素，但实际上先是调用 List.rev，倒转元素的顺序。这是因为我们收集到的元素顺序是“错误的”。添加到累加器列表中的元素总是在前面，成为新的头，所以，最终我们处理的第一个元素，是累加器中的最后一个元素。调用 List.rev 函数倒转列表，这样，最终返回结果的顺序就正确了。这种方法比我们将在 10.2.2 节中见到的，追加元素到尾部，更有效率。

现在，处理 cons cell 的分支是尾递归。第一步处理头中的元素，并更新累加器[2]，生成递归调用[3]，立即返回结果。F# 编译器可以知道递归调用是最后一步，可以采用尾递归优化。

如果我们将它们粘贴到 F# Interactive  中，尝试处理大列表，很容易发现两个版本之间的区别。对于这些函数，递归深度与列表的长度相同，所以，如果我们用na?ve 版本，就会遇到问题：

> let large = [ 1 .. 100000 ] 

val large : int list = [ 1; 2; 3; 4; 5;...]

> large |> map (fun n ->n*n);; 

val it : int list = [1; 4; 9; 16; 25; ...]

> large |> mapN (fun n ->n*n);; 

Process is terminated due toStackOverflowException.

可以发现，对于递归处理函数来说，尾递归是一项重要技术。当然，F# 库包含了处理列表的尾递归函数，所以，并不真的要自己写像在这里实现的映射和筛选。在第六、七和八章，我们已经看到，设计自己的数据结构，写函数来处理它们，是函数编程的关键。

将要创建的许多数据结构，都相当小，但是，而处理的数据量相当大，尾递归是一项重要技术。使用尾递归，可以写出能够正常处理大型数据集的代码。当然，正因为函数不会栈溢出，不能保证函数在合理的时间内完成任务，这就是为什么还需要考虑更有效地处理列表的原因。

10.2.1 用尾递归避免栈溢出（续!）