深度优先搜索的递归方法与堆栈

Question

我有一个如下方法,它搜索一个集合并递归地评估一个条件:

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

或者,这可以使用堆栈来实现,以避免递归,如下所示:

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

我的问题是,与递归版本相比,当树的深度较大时,堆栈版本是否提供了任何性能优势？

Answer 1

我的问题是,与递归版本相比,当树的深度较大时,堆栈版本是否提供了任何性能优势？

是.当树的深度很大时,递归版本比迭代版本慢得多.那是因为递归版本会破坏调用堆栈,导致不可阻挡的堆栈空间异常,并在返回bool之前终止程序.在堆空间耗尽之前,迭代版本不会这样做,并且堆空间可能比堆栈空间大几千倍.

完全没有给出结果显然比在任何有限的时间内给出结果更糟糕.

但是,如果您的问题确实是"堆栈版本在树深处时提供任何好处,但不是那么深,以至于它会打击堆栈",那么答案是:

你已经两种方式编写了程序.运行它,找出来. 不要在两匹马的互联网图片上显示随机的陌生人,并询问哪个更快; 比赛他们然后你会知道.

另外:我倾向于通过编写遍历和产生每个元素的方法来解决您的问题.如果你能写方法IEnumerable<INode> BreadthFirstTraversal(this INode node)和IEnumerable<INode> DepthFirstTraversal(this INode node)那么你就必须编写自己的搜索; 你可以说node.DepthFirstTraversal().Where(predicate).FirstOrDefault()你什么时候想搜索.

Answer 2

首先我们要明确一点：递归不是为了速度。它所做的任何事情都可以通过迭代至少同样快，而且通常更快。递归的好处在于代码的清晰度。

话虽如此，除非您绝对需要尽可能最快的代码（坦率地说，您几乎从不这样做），否则第二个（数据递归）版本甚至不值得考虑，因为它无缘无故地增加了复杂性。它在 C# 中尤其没有价值，因为每个Stack操作都涉及一个方法调用，而消除递归主要是为了摆脱方法调用。您几乎肯定会添加工作，强制方法调用运行时可以使用内置堆栈更有效地处理的内容。

埃里克（Eric）对堆栈溢出提出了一个合理的观点，但为了使其成为一个问题，您需要一棵数千个节点深的树，或者您必须从已经很深的调用堆栈中进行搜索，或者谓词将需要本身是递归的（可能通过触发其他搜索）。对于稍微平衡的树和不会导致更多递归的谓词，堆栈深度不应该成为问题；默认堆栈已经足够大，可以处理相当多的递归，并且可以根据需要做得更大。

尽管如此：我猜，你也是，每个没有实际实现和测试这两个版本的人也是如此。如果你这么在乎，那就抓紧时间吧。