为什么快速排序称为尾递归算法？
Gee*_*eek 6 algorithm complexity-theory tail-recursion quicksort time-complexity
我知道在这个SO答案中写出的尾递归算法是什么.然而,我正在通过麻省理工学院的快速排序算法视频,并在18:30秒教授说这是尾递归算法.我无法连接这是如何尾递归.我们不是在递归的任何步骤进行计算,还是我们？你能解释为什么这被引用作尾递归算法的一个例子.请以我知道递归算法是什么为前提,给出答案.我不清楚的部分是为什么它被称为尾递归？
尾递归与步骤计算无关.它是关于"可以在不构建调用堆栈的情况下评估递归".什么是尾递归给出的例子？这是一个特例.如果你更深入地看一下这个例子,那你可以找到的是
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()的两个分支部分,我们可以在具有更高项目的一侧使用尾递归(基于枢轴位置).
- 你可以把调用堆栈放在你的答案中进一步解释它.对我来说,似乎你需要在两个程序中构建调用堆栈.tailrecsum调用tail递归和调用tailrecsum ....所以调用堆栈正在构建......不是吗？ (2认同)
- @Geek:我只是这个主题的初学者,我正在阅读"计算机程序的结构和解释"(SICP),它可以免费在线获取; 尾递归的概念与"线性递归与迭代"这一主题密切相关.SICP在这里有很多话要说:http://mitpress.mit.edu/sicp/full-text/book/book-ZH-11.html#%_sec_1.2.1.SICP的这个链接非常清楚地解释了它. (2认同)
- recsum和tailrecsum之间的最大区别在于,第一个生成递归过程,而最后一个生成迭代过程.在recsum中,请注意每个调用都需要返回其值,以便它可以求和为x.在最后一次调用recsum并达到基本情况之后,现在需要计算一系列延期添加.因此,必须记住整个呼叫链,直到最后一次呼叫为止.这是线性递归(我给你的SICP链接非常清楚地解释了它). (2认同)
递归函数的第一步是分区。然后，作为最后一步，您在两个分区上调用递归函数。
来自维基百科：
在计算机科学中，尾调用是在另一个过程中发生的子例程调用，作为其最终操作；它可能会产生一个返回值，然后调用过程立即返回该返回值。