scala - 在 Scala 中创建流的递归方法

Question

这是my previous question的后续.

如我 understand以下计算斐波那契数的方法效率低下，因为方法 fib为每个斐波那契数调用，每次调用它都会创建一个新流。

def fib:Stream[Int] =
Stream.cons(1, Stream.cons(1, (fib zip fib.tail) map {case (x, y) => x + y}))

另一方面，尾递归方法(如在 here 中)看起来非常有效，并且可以计算 O(1) 中的每个斐波那契数。

def fib(a:Int, b:Int):Stream[Int] = Stream.cons(a, fib(b, a+b));

现在我得出结论，创建流的递归方法是有效的，当且仅当它们是尾递归的。这是正确的吗？

Answer 1

不，尾递归是为了帮助编译器循环而不是堆叠(全局)，它是一种编译时优化。

问题来自第一个实现，其中多次调用 fib导致多个 Stream 结构，因此一遍又一遍地进行相同的演算。

fib zip fib.tail
//if we are at the 1000, it will compute million Streams

如果您想查看它，请尝试以下操作

var i = 0
def fib:Stream[Int] = {
  i = i + 1
  println("new Stream : " + i)
  Stream.cons(1, Stream.cons(1, (fib zip fib.tail) map {case (x, y) => x + y}))
}