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

本文关键字：堆栈 递归方法 深度优先搜索 | 更新日期: 2023-09-27 18:06:13

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

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

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

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

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

是的。当树的深度很大时，递归版本比迭代版本慢。这是因为递归版本会破坏调用堆栈，导致无法阻止的堆栈外空间异常，并在返回bool之前终止程序。迭代版本不会这样做，直到堆空间耗尽，并且堆空间可能比堆栈空间大数千倍。

根本不给出结果显然比在任何有限的时间内给出结果更糟糕。

然而，如果你的问题真的是"当树很深时，堆栈版本是否有任何好处，但不是很深，以至于它会破坏堆栈"，那么答案是：

您已经用两种方式编写了程序。运行它并找出答案不要在网上随意向陌生人展示两匹马的照片，并询问哪匹马更快；与他们比赛，然后你就会知道。

此外：我倾向于通过编写遍历和生成每个元素的方法来解决您的问题。如果您可以编写方法IEnumerable<INode> BreadthFirstTraversal(this INode node)和IEnumerable<INode> DepthFirstTraversal(this INode node)，那么您不需要编写自己的搜索；当你想搜索时，你可以说node.DepthFirstTraversal().Where(predicate).FirstOrDefault()。

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

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

Eric对堆栈溢出提出了合理的观点，但为了使其成为一个问题，您需要一个数千个节点深的树，或者您必须从已经很深的调用堆栈中进行搜索，或者谓词本身需要递归(可能通过触发其他搜索(。有了一个稍微平衡的树和一个不会引起更多递归的谓词，堆栈深度应该不会成为问题；默认堆栈已经足够大，可以处理相当多的递归，如果需要，还可以做得更大。

尽管说了这么多：我猜，你也是，每个还没有真正实现和测试这两个版本的人也是。如果你那么在乎，那就计时。

第二个版本有几个优点：

通过使用队列而不是堆栈，您可以轻松地从DFS切换到BFS。

如果深度太大，它将抛出一个可以处理的OutOfMemoryException。(我认为StackOverflowException会自动重新抛出(。

性能和内存使用可能会更好，因为递归方法将所有本地变量(包括编译器生成的(保存在调用堆栈上。

相关文章：