为什么快速排序被称为尾递归算法？

Question

为什么快速排序被称为尾递归算法？

algorithmcomplexity-theorytime-complexityquicksorttail-recursion

6

我知道什么是尾递归算法，如这个SO答案中所述。然而我正在学习MIT的快速排序算法视频，在18:30秒处，教授说这是一个尾递归算法。我无法理解这为什么是尾递归。我们在递归的任何一步都没有进行计算，难道不是吗？您能解释一下为什么它被称为尾递归算法吗？请在我已经了解什么是递归算法的前提下回答。我不清楚的部分是为什么它被称为尾递归？

- Geek

2

你看了上一个问题里提到的维基百科文章了吗？ - Andrey

2

@Andrey 是的，我尝试过了，但我发现我所链接的SO上的答案更易懂、更清晰明了。 - Geek

可能是什么是尾递归？的重复问题。一旦您看到17:28处算法的尾递归定义，就清楚了它是尾递归，因为递归步骤的返回值是对自身调用的返回值。 - Ciro Santilli OurBigBook.com

3个回答

4

请查看快速排序的维基页面。那里有一个尾递归版本。

 function quicksort(array, 'left', 'right')

  // If the list has 2 or more items
  if 'left' < 'right'

      // See "Choice of pivot" section below for possible choices
      choose any 'pivotIndex' such that 'left' ≤ 'pivotIndex' ≤ 'right'

      // Get lists of bigger and smaller items and final position of pivot
      'pivotNewIndex' := partition(array, 'left', 'right', 'pivotIndex')

      // Recursively sort elements smaller than the pivot
      quicksort(array, 'left', 'pivotNewIndex' - 1)

      // Recursively sort elements at least as big as the pivot
      quicksort(array, 'pivotNewIndex' + 1, 'right')

根据尾递归的定义，quicksort的最后一个方法调用是它自己，这就是尾递归。但其他一些实现则不是尾递归。

 quicksort(left) + pivot + quicksort(right)

因为在快速排序算法中，最终操作是将数组拆分成已排序的左部分 + 枢轴元素 + 已排序的右部分。

- xiaowl

2

其他人可以确认这个准确性吗？ - Translunar

1

递归函数的第一步是分区。然后，作为最后一步，您在这两个分区上调用递归函数。

来自维基百科：

尾调用是指发生在另一个过程内部的子例程调用，它可能会产生一个返回值，该返回值随即由调用过程立即返回。

- Marcus Johansson

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jaeyong · Accepted Answer

尾递归并不是按步骤计算，而是“可以在不构建调用栈的情况下评估递归”。什么是尾递归？给出了一个特例。如果你深入研究这个例子，你会发现：

def recsum(x):
 if x==1:
  return x
 else:
  return x+recsum(x-1)

为了成功运行上述代码，你需要建立调用栈。但是，

def tailrecsum(x,running_total=0):
  if x==0:
    return running_total
  else:
    return tailrecsum(x-1,running_total+x)

2) 要运行上述代码，您不需要构建调用堆栈，因为已经有了running_total。只需为“原始调用”和递归构建调用堆栈，无需构建调用堆栈，因为计算该函数所需的状态存储在running_total中。

另外，关于快速排序，我认为教授可能是指可以通过“使用”尾递归来优化快速排序。对于qsort（）的两个分支部分，我们可以在基于枢轴位置的较高项的一侧使用尾递归。

enter image description here