Recursive Approach versus Stack for Depth First Search
c#
Solution
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.
Problem
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?