为什么快速排序被称为尾部递归算法？
我知道什么是尾部递归算法作为写在这个答案里。然而，我正在研究这个MIT快速排序算法视频，在18:30秒，教授说这是尾部递归算法。我无法连接这是如何进行尾递归的。我们没有在递归的任何一步进行计算，或者我们是在做计算？你能解释一下为什么这被引用为尾部递归算法的一个例子吗？请将你的答案建立在这样一个前提之上:我知道递归算法是什么。我不清楚的部分是为什么它被称为尾递归？
回答 3
Stack Overflow用户
发布于 2012-08-08 12:25:23
尾递归不是分步骤计算的。它是关于“可以在不构建调用堆栈的情况下计算递归”。什么是尾递归？给出的例子就是这方面的一个特殊情况。如果你更深入地研究这个例子，你会发现
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()的两个分支部分，我们可以在具有较高项的一侧使用尾递归(基于枢轴位置)。
Stack Overflow用户
发布于 2012-08-08 12:25:45
查看一下快速排序的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)因为在quicksort中的最终动作是sorted_left + pivot + sorted_right。
Stack Overflow用户
发布于 2012-08-08 12:02:11
递归函数的第一步是分区。然后，作为最后一步，调用两个分区上的递归函数。
维基百科：
在计算机科学中，尾调用是在另一个过程中发生的子例程调用，作为它的最终动作；它可能产生一个返回值，然后由调用过程立即返回。
https://stackoverflow.com/questions/11864006
复制相似问题
腾讯云开发者
