Enumerable recursion with some extendable control

Introduction

Enumerations and lambda expressions have to a large extent eliminated a lot of the boilerplate code revolving around basic data collection management.  Any structure that can be recursed can, of course, be expressed as a sequence - (albeit sometimes of infinite length).

In most cases where recursion is commonly needed it is normally possible to do so with a simple flattened loop without the need for actually writing recursive method calls.

For those cases where linear performance loss isn't of any real significance and quick, stable, easily readable and manageable code is of more significance a simple extension method leveraging the existing enumeration and lambda expression support can reduce coding time significantly.  

Some background 

In order to utilize this article's content, you need to be familiar with:

- Recursion: A guide by LogiPro101 can be found at http://www.codeproject.com/Articles/32873/Recursion-made-simple   

- Enumerations and yield return:  A guide by Ryan Andrus can be found at http://www.codeproject.com/Articles/19109/IEnumerable-and-Yield-in-NET-2-0 

- Lamda expressions: A crash course by Ronaldo jer can be found at

http://www.codeproject.com/Tips/298963/Understand-Lambda-Expression-in-3-min 

The benefits  

Using .Recurse to recurse code simplifies recursion to a single word expression that can be used on all common data types.  Ideal for those non-performance critical points where writing additional methods or a custom flattening loop or infinite-loop prevention isn't worth the time it takes to create. 

Features include: 

- Recursion from a root node or from a root enumeration (overloads)

- Eliminating duplicate traversal of child notes (option) 

- Returning results only once (option) 

- Use of a public class that indicates depth, count and exposes a list of objects traversed (if duplication detection is enabled) (optional parameter) 

- Support for early enumeration termination by means of the public class (optional parameter) 

And now, the code (copy & paste ready) 

/// <summary>
/// Contains settings related to controlling recursion using the .Recurse extension methods.
/// Not suited for re-use, create a new instance each time you wish to Recurse.
/// </summary>
/// <remarks>
/// This is a class rather than a struct to reduce stack size for nested calls.
/// </remarks>
public class RecurseOptions
{
    /// <summary>
    /// If set to true returns each item, then its first child item and so forth.
    /// If set to false returns all child items in sequence and then all
    /// their child items in sequence before the child items of the next node, etc.
    /// Suited for general shallow structures and thus the default.
    /// </summary>
    public bool TraverseDepthFirst = true;
    /// <summary>
    /// If set to true the root item will be returned.  If set to false the root item will not be returned.
    /// </summary>
    public bool ReturnRootItem = true;
    /// <summary>
    /// If set to true an item's children will only be traversed once.
    /// The item can still be returned multiple times irrespective of this property.
    /// </summary>
    public bool TraverseOnceOnly = false;
    /// <summary>
    /// If set to true an item will only be returned once even if it is found multiple times in the recursion process.
    /// </summary>
    public bool ReturnUniqueOnly = false;
    /// <summary>
    /// Returns true if the Recurse methods will log traversal in the TraversedNodes list.
    /// </summary>
    public bool LogTraversal
    {
        get
        {
            return TraverseOnceOnly || ReturnUniqueOnly;
        }
    }
    /// <summary>
    /// The current call depth of the recursion process.
    /// Setting this manually may break the recursion process.
    /// </summary>
    public int Depth = 0;
    /// <summary>
    /// Keeps count of the amount of elements that have been returned
    /// </summary>
    public int Count = 0;
    /// <summary>
    /// If set to true no additional .Recurse methods will execute in the recursion process.
    /// </summary>
    public bool Terminated = false;
    /// <summary>
    /// This list is used internally to keep track of what nodes have been traversed.
    /// Only created and used when TraverseOnceOnly or ReturnUniqueOnly is set to true.
    /// </summary>
    public object TraversedNodes;        
}
/// <summary>
/// This class contains several common methods for basic recursion tasks.
/// </summary>
public static class RecurseExt
{
    /// <summary>
    /// Returns the item as a single-item enumeration.
    /// </summary>
    /// <remarks>
    /// This is necessary since lambda statements cannot contain yield break or yield return themselves at present.
    /// </remarks>
    public static IEnumerable<T> AsSingleItemEnum<T>(this T item)
    {
        yield return item;
    }
    /// <summary>
    /// Returns root and all items in list and runs Recurse for each item in list recursively
    /// </summary>
    public static IEnumerable<T> Recurse<T>(this T root, Func<T, 
           IEnumerable<T>> list, RecurseOptions options = null)
    {
        if (root == null)
            yield break;
        ///Use default options if none specified
        options = options ?? new RecurseOptions();
        //Create a blank list if we are just starting traversal
        if (options.Depth == 0 && options.LogTraversal)
            options.TraversedNodes = new List<T>();
        bool hasbeenvisited = false;
        //Check if we have been at this node
        if (options.LogTraversal)
            hasbeenvisited = ((List<T>) options.TraversedNodes).Contains(root);
        //If we return unique nodes only, drop out if we have been here
        if (options.ReturnUniqueOnly && hasbeenvisited)
            yield break;
        if (options.Terminated)
            yield break;
        //Mark this node as visited if necessary
        if (options.LogTraversal && !hasbeenvisited)
            ((List<T>)options.TraversedNodes).Add(root);
        //Return the root item if requested
        if (options.ReturnRootItem)
        {
            options.Count++;
            yield return root;
        }
        //If we don't enumerate child nodes multiple times stop here.
        if (options.TraverseOnceOnly && hasbeenvisited)
            yield break;
        options.Depth++;
        if (options.TraverseDepthFirst)
        {
            //We return root items in the TraverseDepthFirst strategy
            options.ReturnRootItem = true;
            foreach (T t in list(root))
                foreach (T t2 in Recurse(t, list, options))
                {
                    yield return t2;
                    if (options.Terminated)
                        break;
                }
        }
        else
        {
            //We don't return root items in the TraverseDepthFirst strategy since we return them first
            options.ReturnRootItem = false;
            foreach (T t in list(root))
                if (!options.ReturnUniqueOnly || !((List<T>)options.TraversedNodes).Contains(t))
                {
                    options.Count++;
                    yield return t;
                }
            foreach (T t in list(root))
                foreach (T t2 in Recurse(t, list, options))
                {
                    yield return t2;
                    if (options.Terminated)
                        break;
                }
        }
        options.Depth--;
    }
    /// <summary>
    /// Returns root and item and runs Recurse for item recursively.
    /// </summary>
    public static IEnumerable<T> Recurse<T>(this T root, 
           Func<T, T> item, RecurseOptions options = null)
    {
        return Recurse(root, t => item(t).AsSingleItemEnum(), options);
    }
    /// <summary>
    /// Returns all items in root and runs Recurse for each item.
    /// </summary>
    public static IEnumerable<T> Recurse<T>(this IEnumerable<T> root, 
           Func<T, IEnumerable<T>> list, RecurseOptions options = null)
    {
        options = options ?? new RecurseOptions();
        //Create a blank list if we are just starting traversal
        if (options.Depth == 0 && options.LogTraversal)
            options.TraversedNodes = new List<T>();
        if (options.TraverseDepthFirst)
        {
            //We return root items in the TraverseDepthFirst strategy
            options.ReturnRootItem = true;
            options.Depth++;
            foreach (T t in root)
                foreach (T t2 in Recurse(t, list, options))
                    yield return t2;
            options.Depth--;
        }
        else
        {
            //We don't return root items in the TraverseDepthFirst strategy since we return them first
            options.ReturnRootItem = false;
            foreach (T t in root)
                if (!options.ReturnUniqueOnly || !((List<T>)options.TraversedNodes).Contains(t))
                {
                    options.Count++;
                    yield return t;
                }
            options.Depth++;
            foreach (T t in root)
                foreach (T t2 in Recurse(t, list, options))
                    yield return t2;
            options.Depth--;
        }
    }
    /// <summary>
    /// Returns all items in root and runs Recurse for each item.
    /// </summary>
    public static IEnumerable<T> Recurse<T>(this IEnumerable<T> root, 
           Func<T, T> item, RecurseOptions options = null)
    {
        return Recurse(root, t => item(t).AsSingleItemEnum(), options);
    }
}  

Demonstrating basic syntax and option usage  

To demonstrate its usage a few examples follow - first on a dictionary (for these examples there is no real need of recursion, it simply demonstrates usage and expected results) and then for a few use cases on common data types.   

Given the dictionary: 

var dict = new Dictionary<int, int?>();
dict[0] = 1;
dict[1] = 2;
dict[2] = 3;
//Will return 0, 1, 2, 3
Console.WriteLine(
    ((int?)0).Recurse(i => i.HasValue && dict.ContainsKey(i.Value) ? dict[i.Value] : null)
    .Aggregate("", (s, i) => s + (s.Length > 0 ? ", " : "") + i.ToString()));
dict[2] = 3;
dict[3] = 0; 

The following code will return a stack overflow: 

Console.WriteLine(
    dict.Keys.Recurse(i => dict[i])
    .Aggregate("", (s, i) => s + (s.Length > 0 ? ", " : "") + i.ToString())); 

The following code will recurse all elements traversing each element only once and return 0, 1, 2, 3:  

Console.WriteLine(
    ((int?)0).Recurse(i => dict[i.Value], new RecurseOptions() { ReturnUniqueOnly = true })
    .Aggregate("", (s, i) => s + (s.Length > 0 ? ", " : "") + i.ToString())); 

The following code will traverse each element only once  but will return it more than once if it is reference multiple times: 

Console.WriteLine(
    ((int?)0).Recurse(i => dict[i.Value], new RecurseOptions() { TraverseOnceOnly = true })
    .Aggregate("", (s, i) => s + (s.Length > 0 ? ", " : "") + i.ToString()));  

You can terminate the process early by instantiating a RecurseOptions class and setting terminated to true early.  As an example the code below retrieves the powers of 2 up to the first one above 1000: 

var ro = new RecurseOptions();
Console.WriteLine(1.Recurse(i => {
        if (i >= 1000)
            ro.Terminated = true;
        return i * 2;
    }, ro).Aggregate("", (s, i) => s + (s.Length > 0 ? ", " : "") + i.ToString()));

You can also use count to stop the process after n elements.  As an example the code below will retrieve the 5 elements in the n * 3 sequence. 

ro = new RecurseOptions();
Console.WriteLine(1.Recurse(i =>
{
    if (ro.Count > 4)
        ro.Terminated = true;
    return i * 3;
}, ro).Aggregate("", (s, i) => s + (s.Length > 0 ? ", " : "") + i.ToString()));

A few practical usage examples 

Check if a class is compiler generated:  

var iscompilergenerated = (type.Recurse(t => t.DeclaringType).Any(
  t => t.IsDefined(typeof(CompilerGeneratedAttribute), false)));

Inform all the parents of an object that something has happened (a DevExpress GridView is used as sample):  

foreach (var o in ((GridView)sender).Recurse(o => o.ParentView as GridView))
    o.LayoutChanged();

Traverse a dataset to get this row and all it's parent rows (assuming all tables only have 0 or 1 parent relationships): 

return row.Recurse(cur => cur.Table.ParentRelations.Count > 0 ? cur.GetParentRow(cur.Table.ParentRelations[0], DataRowVersion.Current) : null);

Enumerate all controls starting from some root and make them invisible: 

Control control = null;//Assign your control here
foreach (var c in control.Recurse(c => c.Controls.Cast<Control>())) c.Visible = false; 

Additional tips

- Recurse<T> is particularly useful for structural recursion.

- You can recurse multiple properties of an object using lambda statements.  Even though you cannot use yield return in lambda statements - Array<T> / List<T> can be returned. 

- Remember that the even tough the compiler auto-detects the type of object you can manually specify a lower base type (such as Control or object<code><code>).

- Aggregate is useful for any type of common aggregation - including output strings.  Definitely not as performance friendly as using a string builder - but it works just fine for simple output tasks. 

History  

• 2012/11/19 - First edition posted.