Joshua Honig Joshua Honig - 1 year ago 95
C# Question

Logical reduction of recursive enumeration

I find myself regularly writing recursive

iterators to implement the same "Descendants" pattern as provided by, for example,
. The pattern I keep implementing is as follows, given a type
with a single-level iterator called

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 (
, and
). 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
method for multiple specific classes. On the downside, this adds an extension method to
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 Source

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))

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download