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

Question

我知道这个 SO answer 中写的尾递归算法是什么。但是，我正在浏览麻省理工学院的快速排序算法视频，在 18:30 秒，教授说这是尾递归算法。我无法连接这是如何尾递归的。我们没有在递归的任何步骤进行计算，还是我们？你能解释一下为什么这被引用为尾递归算法的例子吗？请在我知道什么是递归算法的前提下回答。我不清楚的部分是为什么它被称为尾递归？

Answer 1

尾递归不是逐步计算。它是关于“可以在不构建调用堆栈的情况下评估递归”。什么是尾递归？是这种情况的一个特例。如果你更深入地看这个例子，你会发现

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

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() 的两个分支部分，我们可以在具有更高项目的一侧（基于枢轴位置）使用尾递归。

Answer 2

查看Quicksort的 wiki 页面。有一个尾递归的版本

 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)

因为最后的动作是quicksortsorted_left + pivot + sorted_right

Answer 3

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

来自维基百科：

在计算机科学中，尾调用是在另一个过程中作为其最终动作发生的子例程调用。它可能会产生一个返回值，然后由调用过程立即返回。