CODEWITHSUNDEEP
scalastreamfibonacci
Michael
Michael

Reputation: 10303

Recursive methods to create Streams in Scala

This is a follow-up to my previous question.

As I understand the following method for calculating Fibonacci numbers is inefficient since the method fib is called for each Fibonacci number and each time it is called it creates a new stream.

def fib:Stream[Int] =
  Stream.cons(1, Stream.cons(1, (fib zip fib.tail) map {case (x, y) => x + y}))

On other hand the tail recursive method (as in here) looks quite efficient and calculates each Fibonacci number in O(1)

def fib(a:Int, b:Int):Stream[Int] = Stream.cons(a, fib(b, a+b));

Now I am concluding that recursive methods that create Streams are efficient if and only if they are tail recursive. Is it correct?

Upvotes: 5

Views: 3589

Answers (2)

Daniel C. Sobral
Daniel C. Sobral

Reputation: 297205

I've tried to improve on Andy's answer, but he pretty much nailed it. The first solution is creating a pyramid of streams -- each call to fib creates another fibonacci stream, and each of these new streams will create new stream themselves, and so on.

To be clear, there are three streams resulting from a call to fib:

  • One created by fib in fib zip fib.tail
  • One created by fib.tail in fib zip fib.tail
  • One created by map (remember, map creates a new collection)

Since the first two are calls to fib, they'll create three streams each, and so on.

Here's a rough "picture" of it:

                          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

And this goes on and on. The middle stream is computed using the highest streams to its left and right (fib and fib.tail). Each of them is computed using lower streams on their left and right. Each of these lower streams is computed using streams shown on the last line.

We could continue this on and on, but you can see that, by the time we computed 8, we already have 14 other fibonacci streams going on.

If you change it from def to val, all these new streams disappear, because fib and fib.tail will refer to an existing stream instead of creating new streams. And since no new stream will be created, there will be no further calls to fib and fib.tail.

Now, if you look at the second answer, you'll notice that there is a single fib call, and no map or similar method, so there's no multiplication effect.

Upvotes: 4

Andy Petrella
Andy Petrella

Reputation: 4345

No, tail recursive is to help the compiler looping instead of stacking (globally), it's a compile time optimization.

The problem came from the first implementation where several calls to fib leads to several Stream constructions, so the same calculus are made over and over. 

fib zip fib.tail
//if we are at the 1000, it will compute million Streams

If you want to see it try the following

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

Upvotes: 7

Related Questions