tl;dr;
In C#, do you have guarantees that a lazy iterator function that calls nothing but itself and does have a valid recursion exit condition will not cause a stack overflow?
Detailed question:
I know that as a rule you don't get guarantees of the Tail Call Optimization (TCO) instruction being generated by the C# compiler (or the JIT), so while you may get TCO, there are no guarantees.
Given this recognition of TCO, I'm wondering if lazy iterator functions (using yield return
etc) because of their nature as a coroutine - does each tail call in one even take up stack space? My intuition of coroutines because of their re-entrancy is that each tail call is optimized by default as the ability to jump out of the function and into the next one from the parent's frame instead of creating a new frame seems natural.
Is this behaviour in C#, or do C# iterator functions' recursive calls create a new frame from the current rather than popping out to the parent frame and re-entering with the new parameters?
Example:
public static IEnumerable<IEnumerable<T>> GeneratePermutations<T>(this IEnumerable<T> choices, int numberToChoose)
{
if (numberToChoose == 1)
{
foreach (var choice in choices)
yield return new T[] { choice };
yield break;
}
var subPermutations = choices.SelectMany(choice =>
choices.Where(elem => !EqualityComparer<T>.Default.Equals(elem, choice))
.GeneratePermutations(numberToChoose - 1)
.Select(permutation => (new T[] { choice }).Concat(permutation)));
foreach (var perm in subPermutations)
yield return perm;
}
My intuition is based off in the above example subPermutations
is simply a heaped computation, it seems upon call to iterate it, it can know it's a heaped computation (it is a part of the functions sig that it's an iterator function), and therefore immediately jump out of it's current frame and expanding the heaped computation into a new frame - costing no extra stack space over what was there before the recursive call was attempted...
This intuition may be totally unfounded...
yield return
is recursive anyway, so TCO is not relevant here. It's simply a state machine.public static IEnumerable<int> Foo() { yield return 1; foreach (var n in Foo()) yield return n; }
. If you try to iterate that sequence you'll eventually blow out the stack, and I don't see any particularly good ways of trying to leverage TCO.yield foreach
statement then I could potentially foresee being able to leverage TCO. The only real way to leverage TCO without that is to try to recognize the pattern offoreach
-ing over the recursive call and yielding all of the items exactly, without doing anything else, and that seems like a pretty sketchy idea.