我现在正在学习数据结构和算法。
我的讲义中有一个使用递归方法实现的二叉搜索树的实现。这是一种优雅的方式，但我的问题是，在实际代码中，如果树的高度/深度很大，我是否应该递归地实现二叉搜索树，它会生成很多调用堆栈。
我了解递归是理解许多数据结构概念的关键概念，但您会选择在实际代码中使用递归吗？
4个回答
8
树天生就是递归的。每个节点都代表一个子树，每个节点的子节点又代表该子树的子树，因此递归是最好的选择，尤其是在其他人需要编辑和维护您的代码的实践中。
现在，如果深度成为您的调用堆栈的问题，那么恐怕您的数据结构存在更深层次的问题（可能它非常巨大，或者非常不平衡）。
- Sam I am says Reinstate Monica
4
“我知道递归是理解许多数据结构的关键概念，但您是否会选择在实际编程中使用递归？” 在刚学习递归时，我也有同样的感觉。然而，在软件行业工作了一年多后，我可以说我用递归的概念解决了几个问题。有时候递归更加简洁、易于理解/阅读，并且更好。并且强调上一个答案中的一个观点，树是一种递归数据结构。在我看来，没有其他方法遍历BST :)”
- Chris Dargis
2
很多时候，编译器可以优化你的代码，避免为每个递归调用创建一个新的堆栈帧（例如查找尾递归）。当然，这完全取决于算法和数据结构。如果树是相对平衡的，我认为递归算法不应该引起任何问题。
- Eduardo
0
递归确实是直观和优雅的，它产生的代码清晰而简洁。同样正确的是，某些方法如快速排序、深度优先搜索等在迭代实现时确实很难。 但在实践中，与迭代对应物相比，递归实现几乎总是会变慢，因为所有函数调用（为了真正理解性能损失，建议您学习一下汇编器为单个函数调用执行多少簿记工作）。
我们谈论的优化通常不适用于每个递归方法，许多编译器和解释器甚至不支持它们。
因此，总之，如果您正在编写某些对性能至关重要的东西，例如数据结构，则应避免使用递归（或者如果您确定编译器/解释器已经覆盖了您的情况，则可以使用它）
附注：CLRS（算法导论，第290页，最后一行）建议BST的迭代搜索过程比递归搜索更快。
- mightyWOZ
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接