Handling common recursive functions
I noticed that in my project we often write recursive functions.
My question is, is there a way to create a recursive function as a generic function for each hierarchical structure using recursive iteration?
Maybe I can use a delegate that gets the root and end flag of the recursion?
Any ideas?
Thanks.
I think you need a way to work with hierarchical structures in a generic way ("general" as defined in English, not necessarily as defined in .Net). For example, this is what I wrote once when I needed to get all the controls inside a Windows Form:
public static IEnumerable<T> SelectManyRecursive<T>(this IEnumerable<T> items, Func<T, IEnumerable<T>> selector)
{
if (items == null)
throw new ArgumentNullException("items");
if (selector == null)
throw new ArgumentNullException("selector");
return SelectManyRecursiveInternal(items, selector);
}
private static IEnumerable<T> SelectManyRecursiveInternal<T>(this IEnumerable<T> items, Func<T, IEnumerable<T>> selector)
{
foreach (T item in items)
{
yield return item;
IEnumerable<T> subitems = selector(item);
if (subitems != null)
{
foreach (T subitem in subitems.SelectManyRecursive(selector))
yield return subitem;
}
}
}
// sample use, get Text from some TextBoxes in the form
var strings = form.Controls
.SelectManyRecursive(c => c.Controls) // all controls
.OfType<TextBox>() // filter by type
.Where(c => c.Text.StartWith("P")) // filter by text
.Select(c => c.Text);
Another example: a class Category
where everyone Category
can have ChildCategories
(just like Control
has a collection Controls
) and assuming that rootCategory
directly or indirectly is the parent of all categories
// get all categories that are enabled
var categories = from c in rootCategory.SelectManyRecursive(c => c.ChildCategories)
where c.Enabled
select c;
a source to share
My question is, is there a way to create a recursive function as a generic function for each hierarchical structure using repeated iteration? Maybe I can use a delegate that gets the root and end flag recursive?
Yes. The only thing you need is a delegate function that calculates the list of children for each element. The function terminates when no children return.
delegate IEnumerable<TNode> ChildSelector<TNode>(TNode Root);
static IEnumerable<TNode> Traverse<TNode>(this TNode Root, ChildSelector<TNode> Children) {
// Visit current node (PreOrder)
yield return Root;
// Visit children
foreach (var Child in Children(Root))
foreach (var el in Traverse(Child, Children))
yield return el;
}
Example:
static void Main(string[] args) {
var Init = // Some path
var Data = Init.Traverse(Dir => Directory.GetDirectories(Dir, "*", SearchOption.TopDirectoryOnly));
foreach (var Dir in Data)
Console.WriteLine(Dir);
Console.ReadKey();
}
a source to share
A simpler and more general approach might be to cache the results of a function and only use the "real" function when the result is known - the effectiveness of this approach depends on how often the same set of parameters are used during your recursion.
If you know Perl, you should check the first 4 higher order Perl chapters that are available as EBook, the ideas presented are language independent.
a source to share
It looks like your solution might be using the visitor pattern successfully .
You can create a specific variant of the Visitor Template by creating a hierarchical visitor template .
A bit difficult to discuss here in full, but it should get you started on some research. The basic idea is that you have a class that knows how to navigate the structure, and then you have visitor classes that know how to handle a particular node. You can separate tree traversal from node processing.
a source to share