在这里使用尾随的优势是什么？

Question 1

尾部递归函数调用允许编译器执行通常无法通过常规递归的特殊优化。在尾部递归功能中，递归调用是要执行的最后一件事。在这种情况下，编译器可以重新使用当前堆栈框架，而不是为每个调用分配堆栈框架，而是将尾部收回功能仅使用单个堆栈框架，而不是数百甚至数千个。

这种优化是可能的，因为编译器知道一旦尾递归调用，就不需要以前的变量副本，因为不再需要执行代码。例如，如果遵循递归调用的打印语句，则编译器将需要知道递归呼叫返回后要打印的变量的值，因此无法重复使用堆栈帧。

这是Wiki页面，如果您想了解有关此“节省空间”和堆栈重复使用的更多信息，以及示例：尾声

编辑：我没有解释这是如何适用于QuickSort的吗？好吧，在这篇文章中，有些术语使一切都混淆了（其中有些是完全错误的）。给出的第一个功能（QuickSort）在左侧进行递归调用，右侧是递归调用，然后退出。请注意，右侧的递归电话是功能中发生的最后一件事。如果编译器支持尾部递归优化（上面解释），则只有左呼叫会创建新的堆栈框架；所有正确的调用只需重用当前帧即可。这可以保存一些堆叠框架，但仍然可能会遭受分区形成一系列调用的情况，在尾部递归优化无关紧要的情况下。另外，即使右侧呼叫使用相同的框架，左侧呼叫调用内右侧调用仍然使用堆栈。在最坏的情况下，堆栈深度为N。

所述的第二个版本是不是尾巴递归的QuickSort，而不是循环排序的QuickSort，并且使用循环进行了右排序。实际上，此QuickSort（如其他用户之前描述的那样）不能对其进行尾随递归优化，因为递归调用不是最后执行的事情。这是如何运作的？正确实施后，对QuickSort的第一个调用与原始算法中的左侧调用相同。但是，甚至没有调用右侧递归电话。这是如何运作的？好吧，循环会解决这个问题：它不是对“左右右”进行排序，而是用呼叫对左侧分组，然后通过仅连续排序 右侧的左侧. 。听起来确实很荒谬，但基本上只是整理了很多左边，以至于权利成为单一要素，而不需要整理。这有效地消除了正确的递归，从而使功能降低了递归（如果可以的话，伪递归）。但是，实际实现并非每次都选择左侧。它选择最小的一面。这个想法仍然相同；基本上，它仅在一侧而不是两者都进行递归调用。选择较短的一面将确保堆栈深度永远不会大于log2（n），这是合适的二进制树的深度。这是因为较短的一侧总是将最多是当前数组部分的大小。文章给出的实现并不能确保这一点，因为它可能会遭受“左为整棵树”的最坏情况。如果您愿意做更多的阅读，则本文实际上可以很好地解释它：基于QuickSort的有效选择和部分分类

Question 2

优势，“混合递归/迭代”版本的全部要点，即通过递归处理一个子范围的IE版本，而另一个子范围则是通过迭代进行的，它可以选择要递归处理的两个子范围中的哪个。确保递归深度永远不会超过 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 您提供的伪代码不会尝试比较子范围的长度。在这种情况下，它没有任何好处。不，它并不是真正的“尾部递归”。 QuickSort不可能将其简化为尾部回复算法。

如果您对“ Qsort loguy higuy”一词进行Google搜索，则基于仅将递归仅用于两个子范围之一的递归的想法，您将很容易地找到其他流行的QuickSort实现（C标准库样式）的众多实例。该32位平台的实现使用了〜32的最大深度的显式堆栈，特别是因为它可以保证递归深度将永远不高。（同样，64位平台只需堆栈深度〜64。）

这 QUICKSORT 在这方面，有两个字面递归电话的版本明显更糟，因为重复的不良选择可以使其达到很高的递归深度，直到 N 在最坏的情况下。通过两个递归电话，您无法保证递归深度将受到限制 log2 N. 。智能编译器可能能够将后续呼叫替换为 QUICKSORT 有迭代，即转身你 QUICKSORT 进入你的 TAIL-RECURSIVE-QUICKSORT, ，但要进行子范围的比较，这是不够聪明的。

Question 3

使用Tail-Recursion的优点：=以便编译器优化代码并将其转换为非恢复代码。

与递归相比，非回收代码的优势：=非恢复代码需要比递归的内存更少的内存。这是因为递归消耗的空闲堆栈框架。

这是有趣的部分： - 即使编译器能够理论上进行了优化，在实践中没有。即使是DOT-NET和JAVA等广泛的编译器也不执行优化。

所有代码优化面临的一个问题是调试能力中的牺牲。优化的代码不再对应于源代码，因此无法轻松理解堆栈跟踪和异常细节。高性能代码或科学应用是一回事，但对于大多数消费者应用程序，即使发布后也需要调试。因此，没有进行优化。

请参见：

Question 4

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

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

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个分区，是7个项目，第三个项目中的第三个，第四个项目之后，一切都已排序。

但是分区很少是完美的。结果，并非所有递归都同样深。在我们的示例中，您可能只有三个级别的深处，有些是7或以上（最坏的情况是30）。通过消除一半的递归，您很有可能最大的递归深度将更少。

正如安德烈特（Andreyt）指出的那样，通常将范围进行比较，以确保最大的分区始终是迭代的，并且是最小的。这保证了给定输入和枢轴选择策略的最小递归深度。

但这并非总是如此。有时，人们希望尽快产生结果，或者只想找到和排序前N元素。在这些情况下，他们总是想在第二个分区之前对第一个分区进行分类。即使在这种情况下，消除尾部递归通常也会改善记忆使用量，并且永远不会使情况变得更糟。

Question 5

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



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

这是尾巴递归吗？

Question 6

尾部递归是现代编译器的优化，称为“尾声消除”。当呼叫者/父函数在孩子呼叫完成后在放松阶段中无需执行任何操作时，最后一件事是递归调用本身，那么现代编译器将使用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中的堆栈溢出。