首页 文章

在Scala中创建Streams的递归方法

提问于
浏览 次
5

这是my previous question的后续行动 .

由于我为每个Fibonacci数调用方法 fib ，因此以下计算Fibonacci数的方法效率很低，每次调用它时都会创建一个新流 .

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

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

scala stream fibonacci

2 回答

  • 4

    我试图改进Andy的answer，但他几乎把它钉了起来 . 第一个解决方案是创建一个流金字塔 - 每次调用 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个其他的斐波那契流正在进行中 .

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

    现在，如果你看第二个答案，你会发现有一个 fib 调用，没有 map 或类似的方法，因此没有乘法效应 .

    回复于
  • 7

    不，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}))
}
    回复于

相关问题