10.1.1避免尾递归的堆栈溢出

对于每一个函数调用，运行时分配一个栈帧（stack frame）。这些帧保存在由系统维护的栈中；调用完成，栈帧被删除；如果函数调用其他函数，那么，一个新的帧添加到这个栈的顶部。栈的大小是有限的，所以，太多的嵌套函数调用会耗光了给其他栈帧的空间，就不能再调用下一个函数了。在 .NET 中发生这种情况时，会引发 StackOverflowException 错误；在 .NET 2.0 以及更高版本中，此异常不能被捕获，这将破坏整个过程。

递归是基于递归嵌套调用的，所以，写复杂的递归计算时，经常遇到这样的错误，并不奇怪。（这未必是真实的。在 C# 中，最常见的原因可能是属性意外引用了自身，而不是其应指向的字段。我们忽略这样的错别字引起的意外，只考虑故意递归。）只是为了显示我们讨论的这种情况，我们使用第三章中列表汇总的代码，但使用一个很大的列表。

清单10.1 汇总列表和栈溢出 (F# Interactive)

> let test1 = [ 1 .. 10000 ]    | 创建测试列表

   let test2 = [ 1 .. 100000];;  |

val test1 : int list

val test2 : int list

> let rec sumList(lst) =

     match lst with

     | [] -> 0    [1]

     | hd::tl -> hd+ sumList(tl);;    [2]

val sumList : int list –> int

> sumList(test1)    [3]

val it : int = 50005000

> sumList(test2)    [4]

Process is terminated due toStackOverflowException.

就像每个递归函数一样，sumList 包含终止递归的分支[1]，和递归调用自己的分支[2]。函数在执行递归调用前，完成一定数量的工作，（对列表执行模式匹配，读取尾），然后，执行递归调用（对尾中的数字求和）。最后，用结果进行计算：把保存在头中的值和从递归返回的总和相加。最后一步的细节尤其重要，一会儿就能看到。

正如我们预测的，存在代码停止工作的一个点，如果列表有几万个元素[3]，能正常运行；列表有十万个元素，由于递归太深，F# Interactive 报告异常[4]。图10.1显示发生的情形：图形上面的箭头表示运行的第一部分，在递归调用之前和期间；图形下面的箭头表示递归返回的结果。

图10.1 在计算列表中数字和时的栈帧情况。第一种情况，栈帧在限制之内，因此，操作成功；第二种情况，计算达到极限，并抛出异常。

我们使用符号 [1..] 表示包含从 1 开始的一个系列的列表。第一种情况，F# Interactive 把从 1 到 10000 的列表作为sumList 的参数值，并开始执行。该图显示了每次调用时，栈帧是如何加到栈中的。在这个过程中，每一步取出列表的尾，并用它作为参数值，递归调用 sumList。第一种情况，栈足够大，所以，最终会到达参数为空列表的情况；在第二种情况下，在大约 64000 次调用以后，就用完了所有的空间，运行时达到栈的极限，并引起 StackOverflowException 异常。

无论从左到右的箭头，还是回来的箭头，都做了一些工作。第一部分操作，把列表分解成头和尾两部分，在递归调用之前执行；第二部分操作，把头中的值加到总计中，在递归调用完成后执行。

现在我们已经知道失败的原因了，那该如何做呢？基本思想是这样的：只需要保持栈帧，因为需要在递归调用完成后，做一些工作。在示例中，仍然需要头元素的值，所以，可以将它加到递归调用的结果中。如果函数在递归调用完成后，不需要做任何事情，可以从最后的递归调用直接跳回到调用者，在栈帧之间不使用任何值。我们使用下面的小函数演示一下：

let rec foo(arg) =

  if (arg = 1000) then true

  else foo(arg + 1)

可以看到，foo 函数在 else 分支执行的最后操作就是递归调用，它并不需要对结果做任何处理，直接返回结果。这种递归调用称为尾递归（tail recursion）。实际上，递归最深层的结果是调用 foo(1000)，可直接返回给调用者。

图10.2 递归函数 foo 在递归调用后，不执行任何操作。运行可以直接跳转到调用者（F# Interactive），从最后的递归调用，即 foo(1000)。

在图 10.2 中，可以看到，计算过程中创建的栈帧（从左边到右的跳转），在返回的跳转上，不再使用。这样，栈帧只在递归调用前需要，但是，当从 foo(1) 递归调用 foo(2) 时，就不需要foo(1) 的栈帧了，运行时简单地把它扔掉，节省空间。图 10.3 显示了实际运行的尾递归函数 foo。

图 10.3 尾递归函数的运行。在递归调用期间，栈帧可以丢弃，所以，在运行期间的任一点只需要一帧就够了。

图 10.3 显示了 F# 如何运行尾递归函数。函数是尾递归，在栈上只需要一个位置，这就使得递归版本像迭代求解一样有效。

那么，每个递归函数是否可以改写成尾递归呢？答案是肯定的，但是，通常的方法有点复杂，我们将在 10.3 节讨论。经验法则是这样的：如果函数在每个分支中只执行一个递归调用，就应该能够使用相对简单的技巧。

.NET 生态中的尾递归

编译使用尾递归的函数时，F# 编译器使用两种方法。当函数调用自己（如前面的例子中 foo），把递归代码翻译成等价的、使用命令式循环的代码。几个函数彼此递归调用时，尾调用也会发生。在这种情况下，编译器无法简单地重写代码，并使用特殊的 tailcall 指令，它是直接由中间语言（Intermediate Language，IL）支持的。

在调试配置中，第二个优化默认情况下是关闭的，因为，它使调试复杂化。尤其是，栈帧在尾调用期间被丢弃，这样，在栈跟踪窗口，就看不到它们。可以开启此功能，在项目属性中，选中“生成尾调用”。

由于尾调用是直接由中间语言支持的，C# 编译器也可以识别尾递归调用，并利用这种优化。目前，不这样做，因为C# 开发人员通常以命令式风格设计代码，尾递归并不需要。

这并不是说，对于用 C# 写的代码，运行时不能使用尾调用优化。即使中间语言不包含希望使用尾调用的明确暗示，适时编译器（just-in-time，JIT）也会注意到，可以安全地做到，并继续进行。发生这种情况的规则是复杂的，x86 和 x64 的适时编译器之间是不同的，它们随时会发生改变。在 .NET4.0 中，适时编译器在许多方面都有改进，因此，经常使用尾递归；另外，也从来没有忽略 tailcall 指令，在 .NET 2.0 中，这是偶然情况，特别是 x64 版本。

10.1.1避免尾递归的堆栈溢出