recursion - 快速排序和尾递归优化

Question

在 Introduction to Algorithms p169 它讨论了使用尾递归进行快速排序。

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

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

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

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

就大小而言，堆比堆栈大，为了简单起见，我们假设每次进行函数调用时都会在堆栈上创建一个新的环境(局部变量、参数等)。因此，考虑到堆栈的大小是有限的，如果您进行太多的函数调用，您将耗尽空间，从而导致堆栈溢出。

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

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

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

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

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