19

在Introduction to Algorithms p169中，它谈到了使用尾递归Quicksort。

本章前面的原始快速排序算法是（伪代码）

Quicksort(A, p, r)
{
 if (p < r)
 {
  q: <- Partition(A, p, r)
  Quicksort(A, p, q)
  Quicksort(A, q+1, r)
 }
}

使用尾递归的优化版本如下

Quicksort(A, p, r)
{
 while (p < r)
 {
  q: <- Partition(A, p, r)
  Quicksort(A, p, q)
  p: <- q+1
 }
}

WherePartition根据枢轴对数组进行排序。

不同之处在于第二种算法只调用Quicksort一次来对 LHS 进行排序。

有人可以向我解释为什么第一个算法会导致堆栈溢出，而第二个不会？还是我误解了这本书。

4

5 回答 5

11

首先让我们从一个简短的、可能不准确但仍然有效的堆栈溢出定义开始。

正如您现在可能知道的那样，有两种不同类型的内存在不同的数据结构中实现：堆和堆栈。

就大小而言，堆比堆栈大，为了简单起见，假设每次调用函数时都会在堆栈上创建一个新环境（局部变量、参数等）。因此，鉴于堆栈大小是有限的，如果您进行过多的函数调用，您将耗尽空间，因此您将有堆栈溢出。

递归的问题在于，由于每次迭代都在堆栈上创建至少一个环境，那么您将很快占用有限堆栈中的大量空间，因此堆栈溢出通常与递归调用相关联。

所以有一个叫做尾递归调用优化的东西，每次递归调用都会重用相同的环境，因此堆栈中占用的空间是恒定的，防止堆栈溢出问题。

现在，有一些规则可以执行尾调用优化。首先，每个调用都是完整的，我的意思是如果你中断执行，函数应该能够随时给出结果，在SICP 中，即使函数是递归的，这也称为迭代过程。

如果您分析您的第一个示例，您将看到每次迭代都由两个递归调用定义，这意味着如果您随时停止执行，您将无法给出部分结果，因为结果取决于这些调用最后，在这种情况下，您不能重用堆栈环境，因为总信息在所有这些递归调用之间分配。

但是，第二个示例没有这个问题，A 是常数，并且 p 和 r 的状态可以在本地确定，所以既然要继续进行的所有信息都在那里，那么可以应用 TCO。

于 2013-09-30T15:01:59.473 回答
7

The essence of the tail recursion optimization is that there is no recursion when the program is actually executed. When the compiler or interpreter is able to kick TRO in, it means that it will essentially figure out how to rewrite your recursively-defined algorithm into a simple iterative process with the stack not used to store nested function invocations.
The first code snippet can't be TR-optimized because there are 2 recursive calls in it.

于 2013-09-30T12:40:44.777 回答
5

尾递归本身是不够的。带有 while 循环的算法仍然可以使用 O(N) 堆栈空间，将其减少到 O(log(N))作为CLRS 部分的练习。

假设我们正在使用一种具有数组切片和尾调用优化的语言。考虑这两种算法之间的区别：

坏的：

Quicksort(arraySlice) {
 if (arraySlice.length > 1) {
  slices = Partition(arraySlice)
  (smallerSlice, largerSlice) = sortBySize(slices)
  Quicksort(largerSlice) // Not a tail call, requires a stack frame until it returns. 
  Quicksort(smallerSlice) // Tail call, can replace the old stack frame.
 }
}

好的：

Quicksort(arraySlice) {
 if (arraySlice.length > 1){
  slices = Partition(arraySlice)
  (smallerSlice, largerSlice) = sortBySize(slices)
  Quicksort(smallerSlice) // Not a tail call, requires a stack frame until it returns. 
  Quicksort(largerSlice) // Tail call, can replace the old stack frame.
 }
}

第二个保证永远不需要超过 log2(length) 的堆栈帧，因为 smallSlice 的长度不到 arraySlice 的一半。但是对于第一个，不等式是相反的，它总是需要大于或等于 log2(length) 的堆栈帧，并且在 smallslice 总是长度为 1 的最坏情况下可能需要 O(N) 个堆栈帧。

如果您不跟踪哪个切片更小或更大，您将遇到与第一个溢出情况类似的最坏情况，即使它平均需要 O(log(n)) 堆栈帧。如果您总是先对较小的切片进行排序，那么您将永远不需要超过 log_2(length) 的堆栈帧。

如果您使用的语言没有尾调用优化，则可以将第二个（非堆栈吹）版本编写为：

Quicksort(arraySlice) {
 while (arraySlice.length > 1) {
  slices = Partition(arraySlice)
  (smallerSlice, arraySlice) = sortBySize(slices)
  Quicksort(smallerSlice) // Still not a tail call, requires a stack frame until it returns. 
 }
}

另一件值得注意的事情是，如果你正在实现类似 Introsort 的东西，如果递归深度超过与 log(N) 成比例的某个数字，你将永远不会达到快速排序的 O(N) 最坏情况堆栈内存使用量，所以你技术上不需要这样做。进行这种优化（首先弹出较小的切片）仍然可以提高 O(log(N)) 的常数因子，因此强烈推荐。

于 2017-03-21T13:30:16.743 回答
3

好吧，最明显的观察是：

最常见的堆栈溢出问题 - 定义

The most common cause of stack overflow is excessively deep or infinite recursion.

第二个使用比第一个更少的深度递归（n每次调用的分支而不是n^2），因此它不太可能导致堆栈溢出。

（因此较低的复杂性意味着更少的机会导致堆栈溢出）

但是有人必须补充为什么第二个永远不会导致堆栈溢出而第一个可以。

资源

于 2013-09-30T12:34:32.930 回答
0

好吧，如果您考虑这两种方法的复杂性，第一种方法显然比第二种方法更复杂，因为它同时调用RecursionLHS和RHS ，因此更有可能发生堆栈溢出

注意：这并不意味着绝对没有机会进入SO第二种方法

于 2013-09-30T12:36:47.020 回答