Quicksort和尾递归优化

Question

在算法简介中, p169它讨论了使用尾递归Quicksort.

本章前面的原始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
 }
}

在哪里Partition根据枢轴对阵列进行排序.

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

有人可以向我解释为什么第一个算法可能导致堆栈溢出,而第二个算法不会？或者我误解了这本书.

Answer 1

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

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

就大小而言,堆大于堆栈,为了保持简单,我们可以说每次进行函数调用时,都会在堆栈上创建一个新的环境(局部变量,参数等).因此,鉴于堆栈的大小是有限的,如果你进行太多的函数调用,你将耗尽空间,因此你将有一个堆栈溢出.

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

因此,有一种称为Tail递归调用优化的东西,它将在每次进行递归调用时重用相同的环境,因此堆栈中占用的空间是恒定的,从而防止了堆栈溢出问题.

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

如果你分析你的第一个例子,你会看到每个迭代是由两个递归调用定义的,这意味着如果你在任何时候停止执行你将无法给出部分结果,因为你的结果取决于那些调用要完成,在这种情况下,您无法重用堆栈环境,因为总信息在所有这些递归调用之间分配.

然而,第二个例子没有那个问题,A是常数,p和r的状态可以在本地确定,所以由于所有的信息都在那里,所以可以应用TCO.

Answer 2

尾递归优化的本质是在程序实际执行时没有递归.当编译器或解释器能够启动TRO时,这意味着它将基本上弄清楚如何将递归定义的算法重写为一个简单的迭代过程,而堆栈不用于存储嵌套的函数调用.
第一个代码段无法进行TR优化,因为其中有2个递归调用.

Answer 3

尾递归本身是不够的。使用 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) 的堆栈帧，因为 lesserSlice 的长度不到 arraySlice 的一半。但对于第一个，不等式是相反的，它总是需要大于或等于 log2(length) 个堆栈帧，并且在最坏的情况下可能需要 O(N) 个堆栈帧，其中smallslice 的长度始终为 1。

如果您不跟踪哪个切片较小或较大，您将遇到与第一个溢出情况类似的最坏情况，即使它平均需要 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)) 的常数因子，因此强烈建议这样做。

Answer 4

嗯，最明显的观察结果是：

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

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

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

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

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

来源