Recursive methods to create Streams in Scala

Question

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?

@DanielC.Sobral Could you explain why the 2nd implementation calculates each Fibonacci number in `O(1)` but the 1st one does it in `O(N)` — Michael, Jan 04 '12 at 06:21
Oops sorry... I was talking about the first... Let me remove my comment... — Andy Petrella, Jan 04 '12 at 09:27
Andy has answered it, but I'll try to give a more illustrative example. — Daniel C. Sobral, Jan 04 '12 at 13:01

Andy Petrella · Answer 1 · 2012-01-03T15:30:14.113

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

score 4 · Accepted Answer · edited May 23 '17 at 10:08

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.

Recursive methods to create Streams in Scala

2 Answers2