在Scala中创建Streams的递归方法

发布时间：2020-12-16 18:42:28 所属栏目：安全来源：网络整理

导读：这是 my previous question的后续行动. 在understand中,以下计算斐波纳契数的方法是低效的,因为为每个斐波纳契数调用方法fib,并且每次调用它时都会创建一个新流. def fib:Stream[Int] = Stream.cons(1,Stream.cons(1,(fib zip fib.tail) map {case (x,y) = x

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

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

解决方法

我试图在 Andy的 answer上进行改进,但他几乎把它钉了起来.第一个解决方案是创建一个流金字塔 – 每次调用fib都会创建另一个斐波那契流,这些新流中的每一个都将自己创建新流,依此类推.

要清楚的是,调用fib会产生三个流：

>一个由fib in fib zip.tail创建的
>一个由fib.tail在fib zip fib.tail中创建
>一个由地图创建(记住,地图创建一个新的集合)

由于前两个是对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.

现在,如果你看第二个答案,你会注意到有一个单一的调用,没有地图或类似的方法,所以没有乘法效应.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!