首页 文章

如何在Scala中修复我的Fibonacci流

提问于
浏览 次
8

我定义了一个返回Fibonacci流的函数，如下所示：

def fib:Stream[Int] = {
  Stream.cons(1,
    Stream.cons(2,
      (fib zip fib.tail) map {case (x, y) => println("%s + %s".format(x, y)); x + y}))
}

功能正常但看起来效率低（参见下面的输出）

scala> fib take 5 foreach println
1
2
1 + 2
3
1 + 2
2 + 3
5
1 + 2
1 + 2
2 + 3
3 + 5
8

所以，看起来该函数从一开始就计算出第n个斐波纳契数 . 这是对的吗？你会怎么解决它？

scala stream fibonacci

2 回答

  • 19

    那是因为你使用了 def . 尝试使用 val ：

    lazy val fib: Stream[Int] 
  = 1 #:: 2 #:: (fib zip fib.tail map { case (x, y) => x + y })

    基本上 def 是一种方法;在您的示例中，每次调用方法调用构造新流时都会调用该方法 . def 和 val 之间的区别有been covered on SO before，所以我在此不再赘述 . 如果你来自Java背景，那应该很清楚 .

    这是关于scala的另一个好处;在Java中，方法可能是递归的，但类型和值可能不是 . 在scala中，值和类型都可以是递归的 .

    回复于
  • 14

    你可以用另一种方式做到这一点：

    lazy val fibs = {
  def f(a: Int, b: Int): Stream[Int] = a #:: f(b, a + b)
  f(0, 1)
}
    回复于

相关问题