In C# coroutine is it possible to combine a yield return first of item with forward to another IEnumerable for rest of items?

user_170361 0
Viewed 35

I'm writing a Markov-chain following recursive function, and what I want to do is yield the head item but then forward to or return a different IEnumerable object for the rest of the values.

Basically I'm asking can we avoid having to do the foreach in the following code? Another way to put it is I'm asking if tail-call optimization is possible in C# coroutines.

    private IEnumerable<int> Follow(int source)
    {
        if (source == 0)
            yield break;
        else
        {
            int target = PickTarget(links[source]);

            yield return target;

            // What I'd like to do (doesn't compile):
            //return Follow(target)); 

            // What I seemingly have to do:
            foreach (var next in Follow(target))
                yield return next;
        }
    }

A concern is the big-O complexity of that recursive foreach. Isn't it O(n) = n + (n-1) + (n-2) + (n-3) + ... ?

coroutine ienumerable c#
1 Answers

I realized the obvious solution is to just rewrite the function to not be recursive.

In the context of a coroutine and given the language constraints, writing it in an imperative rather than functional style leads to a shorter (and perhaps clearer) expression of the algorithm.

    private IEnumerable<int> Follow(int source)
    {
        int node = source;

        while (node != 0)
        {
            yield return node;
            node = PickTarget(links[node]);
        }
    }
user_1703610
Related