java - 深度优先搜索(堆栈还是递归？)

Question

对于DFS，你总是必须使用堆栈吗？经过一些研究，我看到有些人实现了递归而不是堆栈迭代，并且似乎产生了相同的结果。

一个比另一个更有效率吗？许多递归算法采用递归运行的二级甚至有时三级辅助方法。

我问的是因为我必须在图上使用 DFS，我一直在尝试进行递归，我想我几乎成功了，但我对任何错误都保持谨慎。

Answer 1

我认为，递归是进行深度优先搜索的更易读的方法，因为您的代码执行遵循您正在实现的想法。另一方面，递归具有一定的风险，因为它使用调用堆栈，该调用堆栈是与存储堆栈数据结构的内存分开的一部分，并且其大小有限。如果您的搜索太深，您将触发 StackOverflowError 并终止执行。

深度限制很难说，因为每个递归步骤所需的内存量取决于递归方法参数的数量和类型，并且我认为调用堆栈的大小在不同的 JVM 版本和供应商之间有所不同。