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?

Answer 1

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