IEnumerable and give return in recursion

Problem

I’m using an IEnumerableT> function to locate controls in a WebForms page.

The procedure is recursive, and I’m having trouble getting the type I want when the yield return returns the recursive call’s value.

The following is my code:

public static IEnumerable<Control> GetDeepControlsByType<T>(this Control control)
{
    foreach(Control c in control.Controls)
    {
        if (c is T)
        {
            yield return c;
        }

        if(c.Controls.Count > 0)
        {
            yield return c.GetDeepControlsByType<T>();
        }
    }
}

This presently results in the error “Cannot convert expression type.” If this function returns type IEnumerableObject>, the code compiles, but the output has the incorrect type.

Is it possible to use yield return and recursion at the same time?

Asked by Jamie Dixon

Solution #1

Yield return must return T, not an IEnumerableT>, inside a method that returns IEnumerableT>.

Replace

yield return c.GetDeepControlsByType<T>();

with:

foreach (var x in c.GetDeepControlsByType<T>())
{
  yield return x;
}

Answered by Marcin Seredynski

Solution #2

Each of the objects returned by the recursive call must be yielded:

public static IEnumerable<Control> GetDeepControlsByType<T>(this Control control)
{
    foreach(Control c in control.Controls)
    {
        if (c is T)
        {
            yield return c;
        }

        if(c.Controls.Count > 0)
        {
            foreach (Control control in c.GetDeepControlsByType<T>())
            {
                yield return control;
            }
        }
    }
}

It’s worth noting that recursing this approach has a cost: you’ll wind up with a lot of iterators, which can be a performance issue if you have a very deep control tree. If you want to avoid this, you must do the recursion within the method to ensure that only one iterator (state machine) is constructed. More information and a sample implementation can be found in this question, however this certainly adds to the complexity.

Answered by Jon Skeet

Solution #3

Using yield return in recursive methods might cause performance issues if the tree is too deep, as Jon Skeet and Colonel Panic point out in their responses.

Here’s a non-recursive extension approach for traversing a sequence of trees in depth first order:

public static IEnumerable<TSource> RecursiveSelect<TSource>(
    this IEnumerable<TSource> source, Func<TSource, IEnumerable<TSource>> childSelector)
{
    var stack = new Stack<IEnumerator<TSource>>();
    var enumerator = source.GetEnumerator();

    try
    {
        while (true)
        {
            if (enumerator.MoveNext())
            {
                TSource element = enumerator.Current;
                yield return element;

                stack.Push(enumerator);
                enumerator = childSelector(element).GetEnumerator();
            }
            else if (stack.Count > 0)
            {
                enumerator.Dispose();
                enumerator = stack.Pop();
            }
            else
            {
                yield break;
            }
        }
    }
    finally
    {
        enumerator.Dispose();

        while (stack.Count > 0) // Clean up in case of an exception.
        {
            enumerator = stack.Pop();
            enumerator.Dispose();
        }
    }
}

RecursiveSelect, unlike Eric Lippert’s method, works directly with enumerators, eliminating the need to invoke Reverse (which buffers the entire sequence in memory).

The OP’s original technique can be modified as follows using RecursiveSelect:

public static IEnumerable<Control> GetDeepControlsByType<T>(this Control control)
{
    return control.Controls.RecursiveSelect(c => c.Controls).Where(c => c is T);
}

Answered by Michael Liu

Solution #4

Others may have given you the proper answer, but I don’t believe conceding will help your case.

Here’s a code piece that accomplishes the same thing without yielding.

public static IEnumerable<Control> GetDeepControlsByType<T>(this Control control)
{
   return control.Controls
                 .Where(c => c is T)
                 .Concat(control.Controls
                                .SelectMany(c =>c.GetDeepControlsByType<T>()));
}

Answered by tymtam

Solution #5

In your second yield return, you must return the items from the enumerator, not the enumerator itself.

public static IEnumerable<Control> GetDeepControlsByType<T>(this Control control)
{
    foreach (Control c in control.Controls)
    {
        if (c is T)
        {
            yield return c;
        }

        if (c.Controls.Count > 0)
        {
            foreach (Control ctrl in c.GetDeepControlsByType<T>())
            {
                yield return ctrl;
            }
        }
    }
}

Answered by Rob Levine

Post is based on https://stackoverflow.com/questions/2055927/ienumerable-and-recursion-using-yield-return