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)
public class RecurseOptions
{
public bool TraverseDepthFirst = true;
public bool ReturnRootItem = true;
public bool TraverseOnceOnly = false;
public bool ReturnUniqueOnly = false;
public bool LogTraversal
{
get
{
return TraverseOnceOnly || ReturnUniqueOnly;
}
}
public int Depth = 0;
public int Count = 0;
public bool Terminated = false;
public object TraversedNodes;
}
public static class RecurseExt
{
public static IEnumerable<T> AsSingleItemEnum<T>(this T item)
{
yield return item;
}
public static IEnumerable<T> Recurse<T>(this T root, Func<T,
IEnumerable<T>> list, RecurseOptions options = null)
{
if (root == null)
yield break;
options = options ?? new RecurseOptions();
if (options.Depth == 0 && options.LogTraversal)
options.TraversedNodes = new List<T>();
bool hasbeenvisited = false;
if (options.LogTraversal)
hasbeenvisited = ((List<T>) options.TraversedNodes).Contains(root);
if (options.ReturnUniqueOnly && hasbeenvisited)
yield break;
if (options.Terminated)
yield break;
if (options.LogTraversal && !hasbeenvisited)
((List<T>)options.TraversedNodes).Add(root);
if (options.ReturnRootItem)
{
options.Count++;
yield return root;
}
if (options.TraverseOnceOnly && hasbeenvisited)
yield break;
options.Depth++;
if (options.TraverseDepthFirst)
{
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
{
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--;
}
public static IEnumerable<T> Recurse<T>(this T root,
Func<T, T> item, RecurseOptions options = null)
{
return Recurse(root, t => item(t).AsSingleItemEnum(), options);
}
public static IEnumerable<T> Recurse<T>(this IEnumerable<T> root,
Func<T, IEnumerable<T>> list, RecurseOptions options = null)
{
options = options ?? new RecurseOptions();
if (options.Depth == 0 && options.LogTraversal)
options.TraversedNodes = new List<T>();
if (options.TraverseDepthFirst)
{
options.ReturnRootItem = true;
options.Depth++;
foreach (T t in root)
foreach (T t2 in Recurse(t, list, options))
yield return t2;
options.Depth--;
}
else
{
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--;
}
}
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;
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;
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.
Michiel du Toit is a software developer based in Bloemfontein, South Africa focusing on development using C# and SQL Server (both WinForms and ASP.NET).