20

我一直在阅读描述如何通过使用尾递归版本来降低快速排序的空间复杂度的文章，但我无法理解这是怎么回事。以下是两个版本：

QUICKSORT(A, p, r)
       q = PARTITION(A, p, r)
       QUICKSORT(A, p, q-1)
       QUICKSORT(A, q+1, r)


TAIL-RECURSIVE-QUICKSORT(A, p, r)
   while p < r
      q = PARTITION(A, p, r)
      TAIL-RECURSIVE-QUICKSORT(A, p, q-1)
      p = q+1

（来源 - http://mypathtothe4.blogspot.com/2013/02/lesson-2-variations-on-quicksort-tail.html）

据我了解，这两种方法都会在数组的左半边和右半边引起递归调用。在这两种情况下，一次只处理一半，因此在任何时候只有一个递归调用会使用堆栈空间。我看不到尾递归快速排序如何节省空间。

上面的伪代码取自文章——http: //mypathtothe4.blogspot.com/2013/02/lesson-2-variations-on-quicksort-tail.html 文章中提供的解释让我更加困惑——

快速排序对给定的子数组进行分区并继续递归两次；一个在左侧子阵列，一个在右侧。这些递归调用中的每一个都将需要其自己的堆栈空间流。此空间用于以某种递归级别存储数组的索引变量。如果我们想象从执行开始到结束都发生这种情况，我们可以看到堆栈空间在每一层都翻了一番。

那么 Tail-Recursive-Quicksort 如何解决所有这些问题呢？

好吧，我们现在只递归一个，而不是递归两个子数组。这消除了在每一层执行时将堆栈空间加倍的需要。我们通过使用 while 循环作为执行相同任务的迭代控制来解决这个问题。我们不需要堆栈来保存两个递归调用的变量集，我们只需更改相同的变量集并对新变量使用单个递归调用。

在常规快速排序的情况下，我看不到堆栈空间如何在每一层执行中翻倍。

注意：- 文章中没有提到编译器优化。

4

6 回答 6

27

尾递归函数调用允许编译器执行常规递归通常无法执行的特殊优化。在尾递归函数中，递归调用是要执行的最后一件事。在这种情况下，编译器可以重新编写代码以简单地重用当前的堆栈帧，而不是为每个调用分配一个堆栈帧，这意味着尾递归函数将只使用一个堆栈帧，而不是数百甚至数千个。

这种优化是可能的，因为编译器知道一旦进行了尾递归调用，就不需要以前的变量副本，因为没有更多的代码可以执行。例如，如果在递归调用之后有一个打印语句，编译器需要知道递归调用返回后要打印的变量的值，因此堆栈帧不能被重用。

如果您想了解有关“节省空间”和堆栈重用实际如何工作的更多信息，请访问 wiki 页面，以及示例：Tail Call

编辑：我没有解释这如何适用于快速排序，是吗？好吧，在那篇文章中抛出了一些术语，这让一切都变得混乱（其中一些完全是错误的）。给定的第一个函数 (QUICKSORT) 在左侧进行递归调用，在右侧进行递归调用，然后退出。请注意，右侧的递归调用是函数中发生的最后一件事。如果编译器支持尾递归优化（上面解释过），只有左边的调用会创建新的栈帧；所有正确的调用只是重用当前帧。这可以节省一些堆栈帧，但仍然会遇到分区创建一系列调用而尾递归优化无关紧要的情况。另外，即使右侧调用使用相同的帧，在右侧调用中仍然使用堆栈。在最坏的情况下，堆栈深度为 N。

描述的第二个版本不是尾递归快速排序，而是一个快速排序，其中只有左排序是递归完成的，右排序是使用循环完成的。事实上，这种快速排序（如另一个用户之前所描述的）不能对其应用尾递归优化，因为递归调用不是最后执行的事情。这是如何运作的？如果正确实施，对快速排序的第一次调用与原始算法中的左侧调用相同。但是，甚至没有调用右侧递归调用。这是如何运作的？好吧，循环会处理这个问题：它不是对“从左到右”进行排序，而是通过调用对左侧进行排序，然后通过仅对右侧的左侧进行连续排序来对右侧进行排序. 听起来真的很可笑，但它基本上只是对这么多的左边进行排序，使右边成为单个元素，不需要排序。这有效地消除了正确的递归，使函数的递归性降低（如果您愿意，可以使用伪递归）。然而，真正的实现并不是每次都只选择左边；它选择最小的一侧。这个想法还是一样的；它基本上只在一侧而不是两侧进行递归调用。选择较短的一边将确保堆栈深度永远不会大于 log2(N)，这是正确二叉树的深度。这是因为较短的边总是最多是我们当前数组部分大小的一半。然而，文章给出的实现并不能确保这一点，因为它可能会遭受同样的最坏情况“基于快速排序的高效选择和部分排序

于 2013-11-08T07:54:34.957 回答
11

“混合递归/迭代”版本的优点，即通过递归处理一个子范围和通过迭代处理另一个子范围的版本，是通过选择两个子范围中的哪一个递归处理，您可以保证递归的深度永远不会超过log2 N，无论枢轴选择有多糟糕。

对于TAIL-RECURSIVE-QUICKSORT问题中提供的伪代码，其中递归处理首先由文字递归调用执行，该递归调用应该被赋予较短的子范围。这本身将确保递归深度将受到限制log2 N。因此，为了保证递归深度，代码在决定通过递归调用处理哪个子范围之前，绝对必须比较子范围的长度。

该方法的正确实现可能如下所示（借用您的伪代码作为起点）

HALF-RECURSIVE-QUICKSORT(A, p, r)
   while p < r
      q = PARTITION(A, p, r)
      if (q - p < r - q)
        HALF-RECURSIVE-QUICKSORT(A, p, q-1)
        p = q+1
      else
        HALF-RECURSIVE-QUICKSORT(A, q+1, r)
        r = q-1

您提供的TAIL-RECURSIVE-QUICKSORT伪代码不会尝试比较子范围的长度。在这种情况下，它没有任何好处。不，它不是真正的“尾递归”。快速排序不可能简化为尾递归算法。

如果你在谷歌上搜索“qsort loguy higuy”这个词，你会很容易找到另一个流行的 QuickSort 实现（C 标准库风格）的大量实例，它们基于仅对两个子范围之一使用递归的相同想法. 32 位平台的该实现使用最大深度为 ~32 的显式堆栈，特别是因为它可以保证递归深度永远不会高于此。（类似地，64 位平台只需要 ~64 的堆栈深度。）

在这方面，进行两次字面递归调用的QUICKSORT版本要差得多，因为重复错误的枢轴选择可以使其达到非常高的递归深度，直到N最坏的情况。使用两次递归调用，您不能保证递归深度会受到log2 N. 一个智能编译器可能能够QUICKSORT用迭代替换尾随调用，即将你QUICKSORT变成你的TAIL-RECURSIVE-QUICKSORT，但它不够聪明，无法执行子范围长度比较。

于 2013-11-08T10:59:18.017 回答
2

使用尾递归的优势 := 以便编译器优化代码并将其转换为非递归代码。

非递归代码优于递归代码的优势：= 非递归代码比递归代码需要更少的内存来执行。这是因为递归消耗的空闲堆栈帧。

有趣的部分来了：- 尽管编译器理论上可以执行优化，但实际上它们不能。甚至像 dot-net 和 java 这样广泛使用的编译器也不执行该优化。

所有代码优化都面临的一个问题是牺牲调试能力。优化后的代码不再与源代码相对应，因此堆栈跟踪和异常详细信息难以理解。高性能代码或科学应用程序是一回事，但对于大多数消费者应用程序来说，即使在发布后也需要调试。因此优化并没有那么大力进行。

请参见：

  1. https://stackoverflow.com/q/340762/1043824
  2. 为什么 .NET/C# 不针对尾调用递归进行优化？
  3. https://stackoverflow.com/a/3682044/1043824
于 2013-11-08T09:27:30.907 回答
0

这里似乎有一些词汇混乱。

第一个版本是尾递归的，因为最后一条语句是递归调用：

QUICKSORT(A, p, r)
  q = PARTITION(A, p, r)
  QUICKSORT(A, p, q-1)
  QUICKSORT(A, q+1, r)

如果你应用尾递归优化，即将递归转换为循环，你会得到第二个，它不再是尾递归：

TAIL-RECURSIVE-QUICKSORT(A, p, r)
  while p < r
    q = PARTITION(A, p, r)
    TAIL-RECURSIVE-QUICKSORT(A, p, q-1)
    p = q+1

这样做的好处是通常需要更少的堆栈内存。这是为什么？为了理解，假设您想对一个包含 31 个项目的数组进行排序。在极不可能的情况下，所有分区都是完美的，即它们在中间拆分数组，您的递归深度将为 4。确实，第一次拆分将产生两个 15 个项目的分区，第二个拆分将产生 7 个项目的两个分区， 3 个项目中的第三个两个，第四个之后的所有内容都已排序。

但分区很少如此完美。因此，并非所有递归都同样深入。在我们的示例中，您可能有一些只有 3 层深，还有一些是 7 层或更多（最坏的情况是 30 层）。通过消除一半的递归，您很有可能会减少最大递归深度。

正如 AndreyT 指出的那样，通常比较范围以确保始终迭代处理最大的分区，并递归处理最小的分区。这保证了给定输入和枢轴选择策略的最小递归深度。

但情况并非总是如此。有时，人们希望尽快产生结果，或者只想查找和排序前 n 个元素。在这些情况下，他们总是希望在第二个分区之前对第一个分区进行排序。即使在这种情况下，消除尾递归通常也会提高内存使用率，而不会使其变得更糟。

于 2013-11-08T11:52:51.443 回答
0

我不知道这是否是提出这个疑问的正确地方，或者我应该发布一个新问题，但我有一个非常相似的疑问。 

void print(int n) {
  if (n < 0) return;
  cout << " " << n;
// The last executed statement is recursive call
  print(n-1);
  print(n-1);
}

这是尾递归吗？

于 2014-03-12T14:22:22.203 回答
0

尾递归是现代编译器完成的优化，称为尾调用消除。当调用者/父函数在子调用完成后的展开阶段无需做任何事情时，最后一件事就是递归调用本身，然后现代编译器使用 goto 和标签进行优化。

示例：我们的版本 -> 将 n 打印到 1

void fun(int n){
if(n==0)
return;
printf("%d\n",n);
fun(n-1)
}

优化后->

void fun(int n){
start:
if(n==0)
return;
printf("%d\n",n);
n=n-1;
goto start;
}

此优化的优点： 1.使用很少的堆栈帧进行尾递归调用 2.消耗更少的内存 3.无需保存过程激活记录，这减少了函数开销。3.不再有分段错误是C/C++和java中的堆栈溢出。

于 2021-09-25T08:29:44.837 回答