Joshua Honig Joshua Honig - 13 days ago 4
C# Question

Logical reduction of recursive enumeration

I find myself regularly writing recursive

IEnumerable<T>
iterators to implement the same "Descendants" pattern as provided by, for example,
XContainer.Descendants
. The pattern I keep implementing is as follows, given a type
Foo
with a single-level iterator called
Children
:

public static IEnumerable<Foo> Descendants(this Foo root) {
foreach (var child in root.Children()) {
yield return child;
foreach (var subchild in child.Descendants()) {
yield return subchild;
}
}
}


This old StackOverflow question suggests the same pattern. But for some reason it feels weird to me to have to reference three levels of heirarchy (
root
,
child
, and
subchild
). Can this fundamental depth-first recursion pattern be further reduced? Or is this an algorithmic primitive of sorts?

The best I can come up with is to abstract the pattern to a generic extension. This doesn't reduce the logic of the iterator pattern presented above, but it does remove the requirement of defining a
Descendants
method for multiple specific classes. On the downside, this adds an extension method to
Object
itself, which is a little smelly:

public static IEnumerable<T> SelectRecurse<T>(
this T root, Func<T, IEnumerable<T>> enumerator) {

foreach (T item in enumerator(root))
{
yield return item;
foreach (T subitem in item.SelectRecurse(enumerator))
{
yield return subitem;
}
}
}

// Now we can just write:
foreach(var item in foo.SelectRecurse(f => f.Children())) { /* do stuff */ }

Answer

You can use an explicit stack, rather than implicitly using the thread's call stack, to store the data that you are using. This can even be generalized to a Traverse method that just accepts a delegate to represent the "get my children" call:

public static IEnumerable<T> Traverse<T>(
    this IEnumerable<T> source
    , Func<T, IEnumerable<T>> childrenSelector)
{
    var stack = new Stack<T>(source);
    while (stack.Any())
    {
        var next = stack.Pop();
        yield return next;
        foreach (var child in childrenSelector(next))
            stack.Push(child);
    }
}

Because this isn't recursive, and thus isn't creating the state machines constantly, it will perform quite a bit better.

Side note, if you want a Breath First Search just use a Queue instead of a Stack. If you want a Best First Search use a priority queue.

To ensure that siblings are returned in the same order as they are returned from the selecor's order, rather than the reverse, just add a Reverse call to the result of childrenSelector.

Comments