Scala新手:递归和stackoverflow错误

Question

作为Scala新手,我正在阅读书籍,文档,并尝试解决http://aperiodic.net/phil/scala/s-99/上发现的问题.似乎正确Scala代码基于不可变值(val)和递归而不是循环和变量,以使并行性更安全并避免需要使用锁.

例如,练习P22(http://aperiodic.net/phil/scala/s-99/p22.scala)的可能解决方案是:

// Recursive.
def rangeRecursive(start: Int, end: Int): List[Int] =
if (end < start) Nil
else start :: rangeRecursive(start + 1, end)

当然这个代码是紧凑的并且看起来很聪明,但是,当然,如果递归的数量很高,你将面临StackOverflow错误(rangeRecusrsive(1,10000),例如没有JVM调整).如果你看一下内置List.range的源代码(https://github.com/scala/scala/blob/v2.9.2/src/library/scala/collection/immutable/List.scala#L1),你我会看到使用循环和变量.

我的问题是如何管理Scala学习内容的影响,这些内容正在促进val和递归,因为知道这些代码会因递归的数量而中断？

Answer 1

Scala的优点在于您可以轻松进入它.开始时,您可以编写循环,并在您使用该语言变得更加舒适时通过递归执行更多操作.你不能用更"纯粹"的函数语言,如Clojure或Haskell来做到这一点.换句话说,您可以适应不变性val,并在以后继续递归.

当你开始递归时,你应该查找尾调用递归.如果递归调用是函数中的最后一次调用,则Scala编译器会将其优化为字节码中的循环.这样,你就不会得到StackOverflowErrors.此外,如果将@tailrec注释添加到递归函数中,编译器将警告您函数是否为尾调用递归.

例如,您问题中的函数不是尾调用递归.看起来调用rangeRecursive是函数中的最后一个,但是当这个调用返回时,它仍然必须附加start到调用的结果.因此,它不能是尾调用递归:它仍然必须在调用返回时工作.