6

考虑这段代码（取自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

它工作得很好。请注意，这sieve实际上不是尾递归（或者是吗？），即使Stream' 的尾是惰性的。

但是这段代码：

def sieve(n: Int): Stream[Int] = {
  n #:: sieve(n + 1).filter(_ % n != 0)
}

val primes = sieve(2)
primes.take(1000).toList

抛出StackOverflowError。

第二个例子有什么问题？我filter想把事情搞砸了，但我不明白为什么。它返回 a Stream，所以它不会使评估变得急切（我是对的吗？）

4

2 回答 2

8

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

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

所以在第一种情况下，调用堆栈的深度是素数的数量，而在第二种情况下，它是最大的素数本身（嗯，减一）。

于 2012-11-11T18:31:18.820 回答
1

这些都不是尾递归的。

使用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)
于 2012-11-11T18:29:47.597 回答