递归和StackOverflowError

Question

你将如何调整这个简单的递归示例,以便发生尾调用优化(而不是a StackOverflowError)？

count 0 = 0
count n = succ (count (pred n))
count 100000

Answer 1

这是我称之为"长度/倍数"类型的堆栈溢出.当应用递归函数来计算构成结果的函数应用程序的strict参数时,会发生这种情况.相比:

-- naive computation of list length
-- this is not like it's defined in Frege, of course
length [] = 0
length (_:xs) = 1 + length xs

foldr f当f第二个参数严格时,也会发生这种情况.

堆栈溢出(SO)还有其他可能的原因:

1. 尾递归.这在Frege中最有效地处理,因为尾递归函数被编译为while循环.与其他JVM语言不同,它永远不会真正导致SO.
2. 显式间接尾递归:(例如a尾调用b,尾调用c,...,尾调用a).这也应该永远不会导致弗雷格的SO.
3. 构建如此深度嵌套的thunk,以便在评估时出现SO.这就是foldlHaskell中发生的事情.在弗雷格,标准fold在累加器中是严格的,因此在许多情况下是免疫的.但是,以下列表仍会在长列表中溢出:fold (<>) mempty (map (Just . Sum) [1..10000])
4. 长度/倍数递归,如我们的示例中所示.
5. 非尾调用中的递归:

以下是最后一个案例:

  even 0 = true
  even n = case even (pred n) of
           true  -> false
           false -> true

第二个等式在语义上等同于4 even n = not (even (pred n)),因此是4的更恶意变体.

要回答您的问题,在您的示例中,可以使用累加器来创建尾递归版本:

count n = go 0 n
    where
       go acc 0 = acc
       go acc n = go (succ acc) (pred n)

或许值得注意的是,你的例子在Haskell中也失败了:

GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> let count 0 = 0; count n = succ (count (pred n))
Prelude> count 10000
10000
Prelude> count 100000
100000
Prelude> count 1000000
1000000
Prelude> count 10000000
10000000
Prelude> count 100000000
*** Exception: stack overflow

它仅以更高的数量溢出的原因是Haskell RTS以更适合函数编程的方式管理RAM,而JVM在启动时分配一个小的默认堆栈,可以容纳几千的调用深度.最好.

当您强制JVM分配更大的堆栈时,即使在Frege中,您也可以使用您的程序计算更多的数字:

java -Xss512m ....

经验表明,512m的堆栈允许单个参数函数的调用深度大约为1000万.

但是,这不是一般解决方案,因为JVM会创建具有此堆栈大小的所有线程.因此浪费了宝贵的RAM.即使你有足够的内存,你也可能无法创建超过2g的堆栈.

在Frege的下一个主要版本中,希望能够更好地管理堆栈溢出类型3和4(见上文)的某些病理情况.但是,截至今天,此类构造仅适用于恰好适合JVM堆栈的小问题大小.