Handling common recursive functions

Question

I've noticed that in my project, we frequently are writing recursive functions.

My question is: is there any way to create the recursive function as generic function for each hierarchy structure that is using the recursive iteration?

Maybe I can use a delegate that gets the root and the end flag of the recursion?

Any ideas?

Thanks.

Answer 1

I'm not sure what exactly your question is asking for but a recursive function can be generic. There's no limitation on that. For instance:

int CountLinkedListNodes<T>(MyLinkedList<T> input) {
   if (input == null) return 0;
   return 1 + CountLinkedListNodes<T>(input.Next);
}

Answer 2

An easier and also generic approach might be to cache the results of the function and use the "real" function only when the result is known - the effectivness of this approach depends how frequently the same set of parameters is used during your recursion.

If you know Perl you should check the first 4 chapters of Higher-Order Perl which are available as a EBook, the ideas presented are language-independent.

Answer 3

It sounds like your solution can successfully use the Visitor Pattern.

You can create a specific variation of the Visitor Pattern by creating a hierarchical visitor pattern.

It is a little complex to discuss entirely here, but that should get you started into some research. The basic idea is that you have a class that knows how to traverse the structure, and then you have Visitor classes that know how to process a particular node. You can separate the traversal of the tree with the processing of nodes.

Answer 4

I think what you want is a way to work with hierarchical structures in a generic way ("generic" as defined in English, not necessarily as defined in .Net). For example, this is something 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 Category class where each Category could have ChildCategories (same way a Control has a Controls collection) and assuming that rootCategory is directly or indirectly 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;

Answer 5

My question is: is there any way to create the recursive function as generic function for each hierarchy structure that is using the recusive iteration? may be i can use a delegate that gets the root and the end flag of the recursive?

Yes - The only thing you need is a delegate function that computes a list of children for each element. The function terminates when no children are returned.

    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();
    }