Make a recursive method faster

Question

How would you refactor this method to make it more performant?

If you have refactored the code you need to prove the performance gain in numbers to get the solution :)

public static T Find<T>(
    this IEnumerable<T> source,
    Func<T, IEnumerable<T>> childrenSelector,
    Predicate<T> condition)
{
    T t = default(T);
    foreach (T item in source)
    {
        if (condition(item))
        {
            return item;
        }

        t = childrenSelector(item).Find<T>(childrenSelector, condition);

        if (!Equals(t, default(T)))
        {
            return t;
        }
    }
    return t;
}

Answer 1

Do you really have a performance issue?

Optimizing a recursive function is usually done by performing tail call optimization, but this is not possible here since you have multiple branchs to explore at each function call.

I would thus not try to make the code faster, but the algorithm faster. If searching in a tree actually slows your code, that means you need to change the way it works so that you know which branch to explore at each function call and having O(log n) complexity instead of O(n). There are tons of trees which have nice properties likes this: B-trees, red-black trees, splay trees and so on. You can also consider using a hash table.