Recursive Approach versus Stack for Depth First Search

Question

I have a method as below which searches a collection and evaluates a condition recursively:

public static bool Recurse(this INodeViewModel node, Func<INodeViewModel,bool> predicate)
{
   INodeViewModel currentNode = node;

   return predicate(currentNode) || node.Children.Select(x => Recurse(x, predicate)).Any(found => found);
}

Alternatively this can be implemented using a stack to avoid recursion as below:

public static bool UsingStack(this INodeViewModel node, Func<INodeViewModel, bool> predicate)
{
   var stack = new Stack<INodeViewModel>();
   stack.Push(node);

   while(stack.Any())
   {
       var current = stack.Pop();

       if (predicate(current))
           return true;

       foreach (var child in current.Children)
       {
           stack.Push(child);
       }
   }
   return false;
}

My question is, does the stack version offer any performance benefits when the depth of the tree is large compared to the recursive version?

Answer 1

My question is, does the stack version offer any performance benefits when the depth of the tree is large compared to the recursive version?

Yes. The recursive version is infinitely slower than the iterative version when the depth of the tree is large. That's because the recursive version will blow the call stack, cause an unstoppable out-of-stack-space exception, and terminate your program before the bool is returned. The iterative version will not do that until heap space is exhausted, and heap space is potentially thousands of times larger than stack space.

Not giving a result at all is obviously worse performance than giving a result in any finite amount of time.

If however your question really is "does the stack version offer any benefit when the tree is deep, but not so deep that it blows the stack" then the answer is:

You've already written the program both ways. Run it and find out. Don't show random strangers on the internet pictures of two horses and ask which is faster; race them and then you'll know.

Also: I would be inclined to solve your problem by writing methods that do traversals and yield each element. If you can write methods IEnumerable<INode> BreadthFirstTraversal(this INode node) and IEnumerable<INode> DepthFirstTraversal(this INode node) then you don't need to be writing your own search; you can just say node.DepthFirstTraversal().Where(predicate).FirstOrDefault() when you want to search.

Answer 2

Let's make this clear first: Recursion is not for speed. Anything it does can be done at least as fast, and often faster, with iteration. Recursion's benefits come in the clarity of the code.

With that said, unless you absolutely need the fastest possible code (and frankly, you almost never do), the second (data-recursive) version isn't even worth considering, as it adds complexity for no good reason. It's especially worthless in C#, as each Stack operation involves a method call, and eliminating recursion is mostly about getting rid of the method calls. You're almost certainly adding work, forcing method calls for stuff that the runtime could handle far more efficiently with the built-in stack.

Eric makes a reasonable point about stack overflows, but in order for that to be an issue, you'd need a tree thousands of nodes deep, or you'd have to be searching from an already deep call stack, or the predicate would need to be recursive itself (possibly by triggering other searches). With an even slightly balanced tree and a predicate that doesn't cause more recursion, stack depth should not be an issue; the default stack is already large enough to handle quite a bit of recursion, and can be made bigger if needed.

With all that said, though: I'm guessing, as are you, as is everyone who hasn't actually implemented and tested both versions. If you care that much, time it.