c++ - 排序算法中的递归 - 总是不好？

Question

合并排序、快速排序可能是最知名的 nlogn 排序算法。他们的解释和 c++ 代码示例在大多数情况下都包含递归。但据我了解，当数据量很大时，我们将面临堆栈溢出的巨大风险。那么忽略关于排序算法的递归解释是否合理，因为它不能在现实生活中使用？

Answer 1

但据我了解，当数据量很大时，我们将面临堆栈溢出的巨大风险。

这取决于几件事：

• 如今，尾调用几乎总是被优化，因此即使您递归O(2^N)时间，您也永远不会在尾递归中遇到堆栈溢出（算法仍然很慢，但不会溢出堆栈）。
• 大多数排序算法都会递归停机Log2(N)时间。每 TB 数据排序最多 40 个级别 - 不足以溢出能够在其内存中保存 TB 数据的任何东西的堆栈。

忽略无法在现实生活中使用的排序算法的递归解释是否合理？

不，忽略这些解释是不合理的：如果算法在逻辑上是递归的，那么最好的解释也是递归的。即使您使用使用动态分配的堆栈来避免堆栈溢出的循环来实现该算法，该算法的性质仍将保持递归，因此了解正在发生的事情的最佳方法是假装进行了递归调用。

Answer 2

使用O(n log n)排序算法，递归算法引起的调用栈高度通常为O(log n)（假设每次递归迭代问题大小划分相对均衡）

异常发生在最坏情况下的快速排序场景中，当数组已经排序时，总是使用最后一个元素作为枢轴的简单实现，在这种情况下，您将有一个O(n^2)运行时间并导致调用堆栈高度为O(n).

（如果它可以帮助您可视化：这有点类似于 DFS 使用比 BFS 更少空间的原理——前者一次只跟踪调用堆栈中的一个“搜索路径”，而后者跟踪所有这些)

Answer 3

在O(n logn)算法中，我们通常关注log2(n)递归级别。

举一个具体的例子，log2(1,000,000,000) = 30因此几乎没有堆栈溢出的主要风险。

如果允许递归深度增长为O(n). 可扩展的算法需要确保不会发生这种情况。

Answer 4

正如其他人指出的那样，堆栈的深度等于最深的递归级别，通常是 order log(n)。

递归的“问题”通常是进行方法调用和传递参数所涉及的开销。例如考虑阶乘方法

int factorial(int k) {if (k==1) return 1 else return k*factorial(k-1);}

如果你用 n=21 调用它，那么你会做 20 次乘法，但你也有设置和从 20 次方法调用返回的开销 - 更多的工作。如果您确实想使用递归算法，您可以设置一个私有堆栈并使用 while 循环来实现该算法，而无需大量（相对昂贵的）方法调用。当然，改进（如果有的话）将是特定于语言的。