12

作为 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），您'会看到使用了循环和变量。

我的问题是如何管理促进 vals 和递归的 Scala 学习内容的影响，因为知道此类代码会因递归次数而中断？

4

4 回答 4

16

Scala 的好处是您可以轻松进入它。一开始，您可以编写循环，并随着您对语言的熟悉程度越来越高，使用递归做更多事情。您不能使用更“纯”的函数式语言（例如 Clojure 或 Haskell）来做到这一点。换句话说，您可以对不可变性和 感到满意val，然后继续进行递归。

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

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

于 2012-07-27T10:51:23.117 回答
4

这是使该方法尾递归的示例。@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,...

它使用一种称为“累加器传递方式”的常用技术，在这种技术中，中间结果被累加并传递到递归的下一步。最底层的步骤负责返回累积的结果。在这种情况下，累加器恰好反向构建其结果，因此基本情况必须反转它。

于 2012-07-27T15:24:35.127 回答
1

如果你重写上面的代码，使它是尾递归的，编译器会将代码优化成一个while循环。@tailrec此外，当注释的方法不是尾递归时，您可以使用注释来获取错误。从而使您知道“什么时候做对了”。

于 2012-07-27T10:53:40.667 回答
1

这是 James 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,...

这不会抛出 a StackOverflowError，因为Stream.cons-operator ( #::) 通过引用存储尾部。换句话说，Stream 元素在stream.toList被调用之前不会被计算。

在我看来，这比累加器模式更具可读性，因为它最类似于朴素的初始算法（只需用::和#::byNil替换Stream.empty）。此外，不需要accum.reverse，这很容易被遗忘。

于 2015-06-28T14:32:18.637 回答