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

我有如下方法，该方法搜索集合并递归评估条件:

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 Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15684330/