Scala Stream call-by-need (lazy) vs call-by-name

Question

So I understand that call-by-need is simply a memoized version of call-by-name. In Martin Odersky's FP Course on Coursera, in lecture 7.3 (Lazy Evaluation), he mentions that if Streams were implemented using call-by-name, then it could potentially lead to a blowup in computational complexity.

What would be an example of such a blowup?

Call-by-name:

def cons[T](hd: T, tl: => Stream[T]) = new Stream[T] {
  def head = hd
  def tail = tl
  ...
}

Call-by-need:

def cons[T](hd: T, tl: => Stream[T]) = new Stream[T] {
  def head = hd
  lazy val tail = tl
  ...
}

Answer 1

For example the Fibonacci series, implemented by adding the previous two elements to form the successor. Without memoization, that would have a linear slowdown (and stack growth) in the length of the sequence:

scala> lazy val fib: Stream[Int] = Stream.cons(0,
     | Stream.cons(1, fib.zip(fib.tail).map(p => p._1 + p._2)))
fib: Stream[Int] = Stream(0, ?)

Example lazily (-sic-) copied from this blog