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

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

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)

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

上面的伪代码摘自文章 -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文章中的解释更让我困惑——

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

那么尾递归快速排序如何解决所有这些问题呢？

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

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

注意：- 本文中没有提及编译器优化。

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

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

如果您想了解有关“空间节省”和堆栈重用实际如何工作的更多信息，请参阅以下 wiki 页面以及示例：尾调用 http://en.wikipedia.org/wiki/Tail_call

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

描述的第二个版本是not尾递归快速排序，而是一种仅递归完成左侧排序，而使用循环完成右侧排序的快速排序。事实上，这个快速排序（如另一个用户之前所描述的）不能应用尾递归优化，因为递归调用不是最后执行的事情。这是如何运作的？当正确实现时，对快速排序的第一次调用与原始算法中的左侧调用相同。然而，甚至没有调用右侧递归调用。这是如何运作的？好吧，循环会处理这个问题：它不是“先左后右”排序，而是通过调用对左侧进行排序，然后通过不断地仅对右侧进行排序来对右侧进行排序。左边的右边的。这听起来确实很荒谬，但它基本上只是对如此多的左元素进行排序，使得右元素变成单个元素，不需要排序。这有效地消除了正确的递归，从而减少了函数的递归性（伪递归，如果你愿意的话）。然而，真正的实现并不是每次都只选择左侧；它选择最小的一侧。想法还是一样的；它基本上只在一侧而不是两侧进行递归调用。选择较短的一侧将确保堆栈深度永远不会大于 log2(N)，这是正确二叉树的深度。这是因为较短的边始终最多是当前数组部分大小的一半。然而，本文给出的实现并不能确保这一点，因为它可能会遇到“左边是整棵树”的相同最坏情况。如果您愿意阅读更多内容，这篇文章实际上对此给出了很好的解释：基于快速排序的高效选择和部分排序 http://blogs.msdn.com/b/devdev/archive/2006/01/18/514482.aspx