How to “unroll” a “recursive” structure

by

I don’t believe there’s anything built into LINQ to do this.

There’s a problem with doing it recursively like this – you end up creating a large number of iterators. This can be quite inefficient if the tree is deep. Wes Dyer and Eric Lippert have both blogged about this.

You can remove this inefficiency by removing the direct recursion. For example:

public static IEnumerable<T> SelectRecursive<T>(this IEnumerable<T> subjects,
    Func<T, IEnumerable<T>> selector)
{
    if (subjects == null)
    {
        yield break;
    }

    Queue<T> stillToProcess = new Queue<T>(subjects);

    while (stillToProcess.Count > 0)
    {
        T item = stillToProcess.Dequeue();
        yield return item;
        foreach (T child in selector(item))
        {
            stillToProcess.Enqueue(child);
        }
    }
}

This will also change the iteration order – it becomes breadth-first instead of depth-first; rewriting it to still be depth-first is tricky. I’ve also changed it to not use Any() – this revised version won’t evaluate any sequence more than once, which can be handy in some scenarios. This does have one problem, mind you – it will take more memory, due to the queuing. We could probably alleviate this by storing a queue of iterators instead of items, but I’m not sure offhand… it would certainly be more complicated.

One point to note (also noted by ChrisW while I was looking up the blog posts 🙂 – if you have any cycles in your friends list (i.e. if A has B, and B has A) then you’ll recurse forever.

Leave a Comment