在 Scala 中创建 Stream 的递归方法

Question

这是我之前的问题的后续问题。

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

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));

现在我得出结论，递归方法当且仅当它们是尾递归时，create Streams 才是高效的。正确吗？

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}))
}

Answer 2

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

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

• 一个由 fib 在 fib zip fib.tail< 中创建/code>
• 由 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 个其他斐波那契流在进行。

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

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