Q:

Understanding recursion in streams

I am trying to understand recursion in streams, it is confusing. My code is this
  val bigIntFromStream : Stream[BigInt] = BigInt(0) #:: BigInt(1) #:: bigIntFromStream.zip(bigIntFromStream.tail).map{x =>
    println(s"stream = ${bigIntFromStream} + stream.tail = ${bigIntFromStream.tail} + zipped value = ${bigIntFromStream.zip(bigIntFromStream.tail)}")
    println(s"Calculating value for ${x}, {x._1} = ${x._1}, {x._2} = ${x._2}")
    x._1 + x._2}

The output for the code is this
0 1 stream = Stream(0, 1, ?) + stream.tail = Stream(1, ?) + zipped value = Stream((0,1), ?)

Calculating value for (0,1), {x._1} = 0, {x._2} = 1
1 stream = Stream(0, 1, 1, ?) + stream.tail = Stream(1, 1, ?) + zipped value = Stream((0,1), ?)

Calculating value for (1,1), {x._1} = 1, {x._2} = 1
2 stream = Stream(0, 1, 1, 2, ?) + stream.tail = Stream(1, 1, 2, ?) + zipped value = Stream((0,1), ?)

Calculating value for (1,2), {x._1} = 1, {x._2} = 2
3 stream = Stream(0, 1, 1, 2, 3, ?) + stream.tail = Stream(1, 1, 2, 3, ?) + zipped value = Stream((0,1), ?)

Calculating value for (2,3), {x._1} = 2, {x._2} = 3
5 stream = Stream(0, 1, 1, 2, 3, 5, ?) + stream.tail = Stream(1, 1, 2, 3, 5, ?) + zipped value = Stream((0,1), ?)

Calculating value for (3,5), {x._1} = 3, {x._2} = 5

My question is how does x get the last value of the zip between the actual value and it's tail? Please tell me if I am missing something 

A:

Recall that a Stream starts out as a single element with a promise to get more if needed. That's the case even if all the elements are fully defined.
val ns = Stream(1,2,3,4,5)
//ns: scala.collection.immutable.Stream[Int] = Stream(1, ?)

And a collection zipped with its own tail effectively pairs each element with its neighbor.
val paired = ns zip ns.tail
//paired: scala.collection.immutable.Stream[(Int, Int)] = Stream((1,2), ?)
// The rest are (2,3), (3,4) and (4,5), but they haven't been realized yet.

Also, when you index a Stream it is a linear operation. In other words, if you want paired(3) the code will step through ("realize") paired(0), and then paired(1), then paired(2), and finally paired(3).
So the Stream you've posted is essentially:
// This is concept, not code.
Stream(a=0, b=1, c=a+b, d=b+c, e=c+d, ...)

Notice that at each index, after the first two, the new element is the sum of 2 previous elements, but those previous elements had to be realized before we could get here, so that's OK. And this is a, potentially, infinite progression, but a Stream only calculates (realizes) an element on request so the elements that aren't requested don't yet exist so they don't take up any memory.

