Scala's Stream 和 StackOverflowError

Question

考虑此代码（从马丁·奥德斯基（Martin Odersky）摘自" Scala中的功能编程原理"课程）：

def sieve(s: Stream[Int]): Stream[Int] = {
  s.head #:: sieve(s.tail.filter(_ % s.head != 0))
}
val primes = sieve(Stream.from(2))
primes.take(1000).toList

它可以正常工作。请注意，即使Stream的尾巴很懒惰，sieve实际上不是尾部递归（还是？）。

但是此代码：

def sieve(n: Int): Stream[Int] = {
  n #:: sieve(n + 1).filter(_ % n != 0)
}
val primes = sieve(2)
primes.take(1000).toList

投掷StackOverflowError。

第二个示例有什么问题？我猜filter弄乱了事情，但我不明白为什么。它返回Stream，因此不会让评估渴望（我对吗？）

Answer 1

您可以通过一些跟踪代码突出显示问题：

var counter1, counter2 = 0
def sieve1(s: Stream[Int]): Stream[Int] = {
  counter1 += 1
  s.head #:: sieve1(s.tail.filter(_ % s.head != 0))
}
def sieve2(n: Int): Stream[Int] = {
  counter2 += 1
  n #:: sieve2(n + 1).filter(_ % n != 0)
}
sieve1(Stream.from(2)).take(100).toList
sieve2(2).take(100).toList

我们可以运行此操作并检查计数器：

scala> counter1
res2: Int = 100
scala> counter2
res3: Int = 540

因此，在第一种情况下，呼叫堆栈的深度是数量的数量，第二个是最大的素数本身（嗯，零之一）。

Answer 2

这些都不是尾部递归。

使用TailRec注释将告诉您功能是否是尾部递归。

将@TaiLrec添加到上面的两个函数中给出：

import scala.annotation.tailrec
@tailrec
def sieve(s: Stream[Int]): Stream[Int] = {
  s.head #:: sieve(s.tail.filter(_ % s.head != 0))
}
@tailrec
def sieve(n: Int): Stream[Int] = {
  n #:: sieve(n + 1).filter(_ % n != 0)
}

加载这表明两个定义不是尾部递归：

<console>:10: error: could not optimize @tailrec annotated method sieve: it contains a recursive call not in tail position
         s.head #:: sieve(s.tail.filter(_ % s.head != 0))
                ^
<console>:10: error: could not optimize @tailrec annotated method sieve: it contains a recursive call not in tail position
         n #:: sieve(n + 1).filter(_ % n != 0)