Stack overflows and recursive sequence expressions F#

Question

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?

[This question](http://stackoverflow.com/questions/15864670/generate-tail-call-opcode), along with answers to it, provides with a rather detailed information what the IL code is being generated. — Be Brave Be Like Ukraine, Jan 16 '15 at 06:08

Petr · Accepted Answer · 2015-01-15T18:17:33.587

4

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

edited Jan 15 '15 at 18:17

answered Jan 15 '15 at 18:06

Petr

4,280
1
19
15

I understand tail call optimization but for that to work the function must use tail recursion as well either through an accumulator or continuation and I'm not seeing how it is implemented in the case here. – Overly Excessive Jan 15 '15 at 21:26
As far as I can see the recursive call to `fibSeq'` is in tail position since nothing in the `fibSeq'` function is executed after this call. To quote the post above: _"Tail Recursion is a specialized type of recursion where there is a guarantee that nothing is left to execute in the function after a recursive call"_ – Christian Jan 15 '15 at 22:27
3

I fail to see how _tail call optimization_ comes into it. Looking with a decompiler, the sequence expression gets compiled into the initial call to the constructor of a compiler-generated class which implements the abstract class `Microsoft.FSharp.Core.CompilerServices.GeneratedSequenceBase`, and each iteration subsequently constructs a new instance of it. Where's the tail call then? – kaefer Jan 16 '15 at 07:31
@keafer There are several ways the F# compiler can optimize code containing tail calls in recursive code: one is to emit the `tail` op code, another is to turn the recursion into a loop using unconditional jumps using the branch instruction `br`. See [here](http://blogs.msdn.com/b/fsharpteam/archive/2011/07/08/tail-calls-in-fsharp.aspx) for more info. – Christian Jan 16 '15 at 15:09
4

@kaefer is right - "tail recursion" in a sequence expression is not really tail recursion since the "recursive" calls are actually interleaved with calls to the sequence's `MoveNext` member. In fact, it's even possible to avoid stack overflows with non-"tail recursive" calls in a computation expression - see http://stackoverflow.com/a/4251497/82959. – kvb Jan 16 '15 at 18:38

Stack overflows and recursive sequence expressions F#

1 Answers1