在Scala中创建Streams的递归方法

Question

这是我上一个问题的后续行动.

据我所知,以下计算Fibonacci数的方法效率很低,因为fib每个Fibonacci数调用该方法,每次调用它时都会创建一个新流.

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

另一方面,尾递归方法(如此处)看起来非常有效并计算每个斐波那契数O(1)

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

现在我得出结论,创建Streams的递归方法是有效的,当且仅当它们是尾递归时.这是对的吗？

Answer 1

不,tail递归是为了帮助编译器循环而不是堆栈(全局),这是编译时优化.

问题来自第一个实现,其中几个调用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}))
}

Answer 2

我试图改进安迪的答案，但他几乎做到了。第一个解决方案是创建一个流金字塔——每次调用都会fib创建另一个斐波那契流，并且每个新流都会自己创建新流，依此类推。

需要明确的是，调用 会产生三个fib流：

• fib一个由in创建fib zip fib.tail
• fib.tail一个由in创建fib zip fib.tail
• 创建者map（记住，map创建一个新集合）

由于前两个是对 的调用fib，因此它们将分别创建三个流，依此类推。

这是它的粗略“图片”：

                          1
                          1
          1               2               1
          1               3       1       2       1
    1     2       1       5       1       3   1   2   1
    1     3   1   2   1   8   1   2   1   5   1   3 1 2 1                          

这种情况一直持续下去。中间流是使用其左侧和右侧的最高流（fib 和 fib.tail）计算的。它们中的每一个都是使用其左侧和右侧的较低流来计算的。这些较低的流中的每一个都是使用最后一行显示的流来计算的。

我们可以继续这样下去，但是你可以看到，当我们计算 8 时，我们已经有 14 个其他斐波那契流在进行。

如果将其从 更改def为val，所有这些新流都会消失，因为fib和fib.tail将引用现有流而不是创建新流。由于不会创建新的流，因此不会进一步调用fib和fib.tail。

现在，如果您查看第二个答案，您会注意到只有一个fib调用，并且没有map或类似的方法，因此没有乘法效应。