递归方法在Scala创建流

Question

这是我上一个问题的后续。

根据我的理解，下面计算斐波那契数的方法是低效的，因为每个斐波那契数都调用fib方法，每次调用它都会创建一个新的流。

deffib:Stream[Int] =流。缺点(1)流。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));

现在我得出结论，创建流的递归方法是有效的当且仅当它们是尾部递归的。对吗?

Answer 1

没有,尾递归是帮助编译器循环而不是堆积(全球),这是一个编译时优化。

这个问题来自于第一个实现，其中对fib的几个调用导致了几个流结构，所以相同的演算是一次又一次地进行。

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在fib zip fib.tail
中创建的一个
• fib.tail在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个其他的fibonacci流在进行。

如果你把它从def改为val，所有这些新的流都消失了，因为fib和fib.tail将引用现有的流，而不是创建新的流。由于不会创建新的流，因此不会再调用fib和fib.tail。

现在，如果你看一下第二个答案，你会注意到只有一个fib调用，没有map或类似的方法，所以没有乘法效应。