CODEWITHSUNDEEP
recursionf#fibonaccitail-recursionlazy-sequences
Overly Excessive
Overly Excessive

Reputation: 2125

Stack overflows and recursive sequence expressions F#

I have a sequence expression like so:

let fibSeq = 
    let rec fibSeq' a b = 
        seq { yield a
              yield! fibSeq' b (a + b) }
    fibSeq' 1 1

Now even for large numbers, this will not generate a stack overflow. I'm wondering why, it seems to me that to generate n Fibonacci numbers with this sequence expression each recursive call would need to return back to the caller eventually to "fold" itself into the sequence. Is there some sort of optimization going on behind the scenes here?

Upvotes: 5

Views: 860

Answers (1)

Petr
Petr

Reputation: 4280

Yes, it's called "Tail Call Optimization" See here: http://blogs.msdn.com/b/chrsmith/archive/2008/08/07/understanding-tail-recursion.aspx Also Seq is lazy so its 500th member will not be evaluated until you will not have to access it in your program like:

let elm = Seq.nth 500 fibSeq

Upvotes: 4

Related Questions