10.1.1避免尾递归的堆栈溢出 对于每一个函数调用,运行时分配一个栈帧(stack frame)。这些帧保存...

来源:互联网 时间:1970-01-01

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 版本。

相关阅读:
Top