Logical reduction of recursive enumeration

Question

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 1

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.

Answer 2

I think this is a good question. The best explanation I have for why you need two loops: We need to recognize the fact that each item is converted to become multiple items (itself, and all its descendants). This means that we do not map one-to-one (like Select) but one-to-many (SelectMany).

We could write it like this:

public static IEnumerable<Foo> Descendants(this IEnumerable<Foo> items) {
 foreach (var item in items) {
  yield return item;
  foreach (var subitem in item.Children().Descendants())
   yield return subitem;
 }
}

Or like this:

public static IEnumerable<Foo> Descendants(Foo root) {
 var children = root.Children();
 var subchildren = children.SelectMany(c => c.Descendants());
 return children.Concat(subchildren);
}

Or like this:

public static IEnumerable<Foo> Descendants(this IEnumerable<Foo> items) {
 var children = items.SelectMany(c => c.Descendants());
 return items.Concat(children);
}

The versions taking an IEnumerable<Foo> must be invoked on root.Children().

I think all of these rewrites expose a different way of looking at the problem. On the other hand, they all have two nested loops. The loops can be hidden in helper functions but they still exist.

Answer 3

I would manage this with a List:

public static IEnumerable<Foo> Descendants(this Foo root) {
    List<Foo> todo = new List<Foo>();
    todo.AddRange(root.Children());
    while(todo.Count > 0)
    {
        var first = todo[0];
        todo.RemoveAt(0);
        todo.InsertRange(0,first.Children());
        yield return first;
    }
}

Not recursive, so shouldn't blow the stack. You just always add more work for yourself onto the front of the list and so you achieve the depth-first traversal.

Answer 4

Both Damien_the_Unbeliever and Servy have presented versions of an algorithm that avoid creating a recursive call stack by using collections of one type or another. Damien's use of a List could cause poor performance to inserts at the head of the list, while Servy's use a of stack will cause nested elements to be returned in reverse order. I believe manually implementing a one-way linked list will maintain Servy's performance while still returning all the items in the original order. The only tricky part is initializing the first ForwardLinks by iterating the root. To keep Traverse clean I moved that to a constructor on ForwardLink.

public static IEnumerable<T> Traverse<T>(
    this T root, 
    Func<T, IEnumerable<T>> childrenSelector) {

    var head = new ForwardLink<T>(childrenSelector(root));

    if (head.Value == null) yield break; // No items from root iterator

    while (head != null)
    {
        var headValue = head.Value;
        var localTail = head;
        var second = head.Next;

        // Insert new elements immediately behind head.
        foreach (var child in childrenSelector(headValue))
            localTail = localTail.Append(child);

        // Splice on the old tail, if there was one
        if (second != null) localTail.Next = second;

        // Pop the head
        yield return headValue;
        head = head.Next; 
    }
}

public class ForwardLink<T> {
    public T Value { get; private set; }
    public ForwardLink<T> Next { get; set; }

    public ForwardLink(T value) { Value = value; }

    public ForwardLink(IEnumerable<T> values) { 
        bool firstElement = true;
        ForwardLink<T> tail = null;
        foreach (T item in values)
        {
            if (firstElement)
            {
                Value = item;
                firstElement = false;
                tail = this;
            }
            else
            {
                tail = tail.Append(item);
            }
        }
    }

    public ForwardLink<T> Append(T value) {
        return Next = new ForwardLink<T>(value);
    } 
}

Answer 5

I propose a different version, without using yield:

    public abstract class RecursiveEnumerator : IEnumerator {
        public RecursiveEnumerator(ICollection collection) {
            this.collection = collection;
            this.enumerator = collection.GetEnumerator();
        }

        protected abstract ICollection GetChildCollection(object item);

        public bool MoveNext() {
            if (enumerator.Current != null) {
                ICollection child_collection = GetChildCollection(enumerator.Current);
                if (child_collection != null && child_collection.Count > 0) {
                    stack.Push(enumerator);
                    enumerator = child_collection.GetEnumerator();
                }
            }
            while (!enumerator.MoveNext()) {
                if (stack.Count == 0) return false;
                enumerator = stack.Pop();
            }
            return true;
        }

        public virtual void Dispose() { }

        public object Current { get { return enumerator.Current; } }

        public void Reset() {
            stack.Clear();
            enumerator = collection.GetEnumerator();
        }

        private IEnumerator enumerator;
        private Stack<IEnumerator> stack = new Stack<IEnumerator>();
        private ICollection collection;
    }

Usage example

    public class RecursiveControlEnumerator : RecursiveEnumerator, IEnumerator {
        public RecursiveControlEnumerator(Control.ControlCollection controlCollection)
            : base(controlCollection) { }

        protected override ICollection GetChildCollection(object c) {
            return (c as Control).Controls;
        }
    }

Answer 6

To expand on my comment, this should work:

public static IEnumerable<Foo> Descendants(this Foo node)
{
    yield return node; // return branch nodes
    foreach (var child in node.Children())
        foreach (var c2 in child.Descendants())
            yield return c2; // return leaf nodes
}

That should will return all branch nodes and leaf nodes. If you only want to return leaf nodes, remove the first yield return.

In response to your question, yes it is an algorithmic primitive, because you definitely need to call node.Children(), and you definitely need to call child.Descendants() on each child. I agree that it seems odd having two "foreach" loops, but the second one is actually just continuing the overall enumeration, not iterating the children.

Answer 7

Try this:

private static IEnumerable<T> Descendants<T>(
    this IEnumerable<T> children, Func<T, IEnumerable<T>> enumerator)
{
    Func<T, IEnumerable<T>> getDescendants =
        child => enumerator(child).Descendants(enumerator);

    Func<T, IEnumerable<T>> getChildWithDescendants =
        child => new[] { child }.Concat(getDescendants(child));

    return children.SelectMany(getChildWithDescendants);
}

Or if you prefer the non Linq variant:

private static IEnumerable<T> Descendants<T>(
    this IEnumerable<T> children, Func<T, IEnumerable<T>> enumerator)
{
    foreach (var child in children)
    {
        yield return child;

        var descendants = enumerator(child).Descendants(enumerator);

        foreach (var descendant in descendants)
        {
            yield return descendant;
        }
    }
}

And call it like:

root.Children().Descendants(f => f.Children())