我现在正在学习数据结构和算法。
我的讲义有一个使用递归方法实现的二叉搜索树的实现。这是一种优雅的方式，但我的问题是在现实生活中的代码中，如果我递归地实现二叉搜索树，如果树的高度/深度数很大，它会生成大量调用堆栈吗？
我知道递归是理解许多数据结构概念的关键概念，但是您会选择在现实生活中的代码中使用递归吗？
问问题
3269 次
4 回答
7
树本质上是递归的。树的每个节点代表一个子树，每个注释的每个子节点代表该子树的一个子树，因此递归是最好的选择，尤其是在其他人可能必须编辑和维护您的代码的实践中。
现在，如果深度成为您的调用堆栈的问题，我担心您的数据结构存在更深层次的问题（或者它非常巨大，或者非常不平衡）
于 2012-07-12T15:40:10.407 回答
3
“我知道递归是理解大量数据结构的关键概念，但你会选择在现实生活中的代码中使用递归吗？”
在第一次学习递归之后，我也有同样的感觉。但是，在软件行业工作了一年多，我可以说我已经使用递归的概念解决了几个问题。很多时候递归更干净，更容易理解/阅读，而且更好。为了强调上一个答案中的一点，树是一种递归数据结构。IMO，没有其他方法可以遍历 BST :)
于 2012-07-12T15:45:52.890 回答
2
很多时候，编译器可以优化您的代码，以避免为每个递归调用创建一个新的堆栈帧（例如，查找尾递归）。当然，这完全取决于算法和您的数据结构。如果树是合理平衡的，我认为递归算法不会引起任何问题。
于 2012-07-11T15:37:52.623 回答
0
确实，递归是直观而优雅的，它产生的代码清晰简洁。某些方法（例如快速排序、DFS 等）确实很难迭代实现，这也是正确的。但实际上，由于所有函数调用，与迭代实现相比，递归实现几乎总是很慢（为了真正理解性能损失，我建议您了解汇编程序必须为单个函数调用做多少簿记工作）。
我们谈论的优化通常不适用于每种递归方法，许多编译器和解释器甚至不支持它们。
所以总而言之，如果您正在编写一些对性能至关重要的东西，例如数据结构，那么请远离递归（或者如果您确定您的编译器/解释器已经涵盖了您，则可以使用它）
PS：CLRS（算法简介，第 290 页，最后一行）表明 BST 的迭代搜索过程比递归搜索过程更快。
于 2018-05-20T16:34:00.823 回答