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

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对给定的子数组进行分区并继续递归两次; 一个在左子阵列上,一个在右侧.这些递归调用中的每一个都需要其自己的堆栈空间流.此空间用于在某种递归级别存储数组的索引变量.如果我们想象这是从执行的开始到结束发生的,我们可以看到堆栈空间在每一层加倍.

那么Tail-Recursive-Quicksort如何修复所有这些呢？

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

在常规快速排序的情况下,我没有看到堆栈空间在每个执行层都是如何加倍的.

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

Answer 1

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

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

这里是维基页面,如果你想了解更多关于如何"节省空间"和堆栈重用实际工作的信息,以及示例:尾部调用

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

描述的第二个版本不是尾递归快速排序,而是一个快速排序,其中只有左排序是递归完成的,并且正确的排序是使用循环完成的.实际上,这个快速排序(如前面另一个用户所描述的)不能对其应用尾递归优化,因为递归调用不是最后执行的操作.这是如何运作的？正确实现时,对quicksort的第一次调用与原始算法中的左侧调用相同.但是,甚至没有调用右侧递归调用.这是如何运作的？好吧,循环处理:不是排序"左,然后",而是通过调用对左边进行排序,然后通过连续排序右边的左边来排序右边.这听起来真的很荒谬,但它基本上只是排序了很多左派,权利成为单一元素,不需要排序.这有效地消除了正确的递归,使得函数不那么递归(伪递归,如果你愿意的话).但是,真正的实现并不是每次只选择左侧; 它选择最小的一面.这个想法仍然是一样的; 它基本上只在一侧进行递归调用而不是两者.挑选较短的一侧将确保堆栈深度永远不会大于log2(N),这是正确的二叉树的深度.这是因为短边总是最多只是当前阵列部分的一半.然而,本文给出的实现并不能确保这一点,因为它可能遭受同样的最坏情况"基于快速排序的高效选择和部分排序

Answer 2

优点,"混合递归/迭代"版本的整个点,即通过递归处理一个子范围的版本和通过迭代处理另一个子范围的版本,是通过选择递归处理两个子范围中的哪一个,您可以保证递归的深度永远不会超过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"进行谷歌搜索,您将很容易找到另一个流行的QuickSort实现(C标准库样式)的大量实例,基于两个子范围中只有一个使用递归的相同想法.32位平台的实现使用最大深度为~32的显式堆栈,因为它可以保证递归深度永远不会高于此值.(同样,64位平台只需要64位的堆栈深度.)

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