# Make a recursive method faster

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

• How can one "prove the performance gain in numbers" if you do not give us a concrete example? Also: stackoverflow.com/tags/performance/info Good question states performance goals that need to be achieved as well as other restrictions. Trying to optimize something without measuring is not "performance" question or work, but most likely personal entertainment - expect question without goals/measurements to be treated as such. Feb 29, 2012 at 14:09
• use the method with a closed generic type and search a 100000 object tree for a certain items property value. Do the same with your optimization on the method then rerun the test. Compare both results and show them here. Thats about the numbers. :) Feb 29, 2012 at 22:39

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.

• Not a real performance issue. But when I want to replace concrete methods to use a generic version my colleagues will ask about the speed ;P Thanks for the B-Tree search tip. I think the road ends here. Feb 29, 2012 at 22:48
• I'd like to mention that a binary search tree is easy to implement, and you should go that way first if you have an issue with your tree. Other data structures avoid certain pitfalls of binary search trees, but they're not that common. Mar 1, 2012 at 8:01
• Is a B-Tree the same as a msdn.microsoft.com/en-us/library/ms379573(v=vs.80).aspx (Binary Search tree) ? Mar 1, 2012 at 9:40
• Nope, a a B-Tree is more complicated and is used in databses such as a CouchDB. Mar 1, 2012 at 9:57