algorithm - 在这里使用尾递归有什么好处？

Question

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

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 文章中提供的解释让我更加困惑 -

Quicksort partitions a given sub-array and proceeds to recurse twice; one on the left-sub-array and one on the right. Each of these recursive calls will require its own individual stream of stack space. This space is used to store the indexing variables for the array at some level of recursion. If we picture this occurring from beginning to end of execution, we can see that the stack space doubles at each layer.

So how does Tail-Recursive-Quicksort fix all of this?

Well, instead of recursing on two sub-arrays, we now only recurse on one. This eliminates the need for doubling stack space at every layer of execution. We get around this problem by using the while loop as an iterative control that performs the same task. Instead of needing the stack to save sets of variables for two recursive calls, we simply alter the same set of variables and use the single recursive call on new variables.

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

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

Answer 1

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

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

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

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

所描述的第二个版本不是尾递归快速排序，而是一种快速排序，其中只有左排序是递归完成的，而右排序是使用循环完成的。事实上，这个快速排序(正如之前另一个用户所描述的)不能对其应用尾递归优化，因为递归调用不是最后执行的事情。这是如何运作的？正确实现后，对快速排序的第一次调用与原始算法中的左侧调用相同。但是，甚至没有调用右侧递归调用。这是如何运作的？好吧，循环会处理这个问题:它不是“先左后右”排序，而是通过调用对左边进行排序，然后通过不断地只对右边的 左边进行排序 来对右边进行排序。听起来真的很可笑，但它基本上只是对这么多左边进行排序，以至于右边变成了单个元素，不需要排序。这有效地删除了正确的递归，使函数的递归性降低(如果你愿意，可以是伪递归)。然而，真正的实现并不是每次都只选择左侧；它选择最小的边。这个想法仍然是一样的；它基本上只在一侧而不是两侧进行递归调用。选择较短的一侧将确保堆栈深度永远不会大于 log2(N)，这是一个适当的二叉树的深度。这是因为较短的边总是最多是我们当前数组部分大小的一半。然而，本文给出的实现并不能确保这一点，因为它可能会遇到“剩下的是整棵树”的最坏情况。如果您愿意阅读更多内容，这篇文章实际上给出了很好的解释:Efficient selection and partial sorting based on quicksort