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学习东西的影响，它促进vals和递归，知道这样的代码可能因递归次数而中断？

Answer 1

关于Scala的好处是您可以轻松进入它。开始时，您可以编写循环，并随着您对该语言的使用变得更加舒适，使用递归进行更多操作。你不能用更纯粹的功能语言如Clojure或Haskell来做到这一点。换句话说，你可以适应不变性和val，然后继续递归。

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

例如，您问题中的函数不是尾调用递归。它看起来像rangeRecursive的调用是该函数中的最后一个，但是当此调用返回时，它仍然必须将start附加到调用的结果。因此，它不能是尾调用递归的：它在调用返回时仍然需要工作。

Answer 2

如果您重写上面的代码以使其成为尾递归，编译器会将代码优化为while循环。另外，您可以使用@tailrec注释在注释的方法不是尾递归时发生错误。从而让你知道“你什么时候做对了”。

Answer 3

下面是一个使该方法尾递归的示例。 @tailrec注释是不必要的，编译器会在没有它的情况下进行优化。但是让它在编译器无法执行优化时会标记错误。

scala> def rangeRecursive(start: Int, end: Int): List[Int] = { 
    | @scala.annotation.tailrec 
    | def inner(accum : List[Int], start : Int) : List[Int] = { 
    |  if (end < start) accum.reverse 
    |  else inner(start :: accum, start + 1) 
    | } 
    | 
    | inner(Nil, start) 
    | } 
rangeRecursive: (start: Int,end: Int)List[Int] 

scala> rangeRecursive(1,10000) 
res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,... 

它使用所谓的“累加器传递风格”，其中中间结果被累积，并传递给在递归下一步骤的常用技术。最下面的步骤是负责返回累计结果。在这种情况下，累加器恰好向后建立其结果，因此基本情况必须将其倒转。

Answer 4

这里是詹姆斯IRY的答案的替代，具有相同的行为：

def rangeRecursive(start: Int, end: Int): List[Int] = { 
    def inner(start : Int) : Stream[Int] = { 
     if (end < start) Stream.empty 
     else start #:: inner(start + 1) 
    } 

    inner(start).toList 
} 

scala> rangeRecursive(1,10000) 
res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,... 

这不会引发StackOverflowError因为Stream.cons - 运算符（#::）存储引用的尾巴。换句话说，在调用stream.toList之前不会计算流元素。

在我看来，这是比蓄电池模式更具有可读性，因为它最接近天真的初始算法（只是Stream.empty取代::通过#::和Nil）。另外，不需要accum.reverse，这很容易被遗忘。