我知道一个尾递归算法就是为written out in this SO answer。不过,我正在通过这video of quick sort algorithm from MIT和18:30秒教授说,这是尾递归算法。我无法连接这是如何尾部递归。我们不是在递归的任何步骤进行计算,还是我们?你能解释为什么这被引用作为尾递归算法的一个例子。请根据您的答案,我知道什么是递归算法。我不清楚的部分是为什么它被称为尾递归?为什么快速排序称为尾递归算法?
回答
递归函数的第一步骤(S)为分区。然后,作为最后一步,您可以在两个分区上调用递归函数。
维基百科:
在计算机科学中,尾部呼叫是一个子程序调用发生这种情况 内的另一个程序作为其最后行动;它可能会产生一个返回 的值,然后立即由调用过程返回。
尾递归是不是在步计算。这是关于“递归可以在没有构建调用堆栈的情况下进行评估”。 What is tail recursion?给出的例子就是一个特例。如果你更深入地看例子,你会发现
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中。
而且,关于快速排序,我认为教授很可能意味着,快速排序可以通过“使用”尾recusion进行优化。对于qsort()的两个分支部分,我们可以在具有较高项目的一侧使用尾递归(基于枢轴位置)。
你可以把你的答案中的调用堆栈进一步解释。对我来说,你似乎需要在这两个过程中构建调用堆栈。 tailrecsum调用尾递归和调用tailrecsum ....所以调用堆栈正在建立...是不是 ? – Geek 2012-08-08 15:06:00
这是我以前的评论的延续......编译器如何在不构建堆栈的情况下计算递归调用? “构建调用堆栈”的含义是多少? – Geek 2012-08-08 15:16:15
@Geek:我只是这个主题的初学者,我正在阅读“计算机程序结构和解释”(SICP),它可以免费在线使用;尾递归的概念与“线性递归与迭代”主题密切相关。 SICP在这里有很多话要说:http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1。来自SICP的这个链接非常清楚地解释它。 – favq 2012-08-09 00:08:45
看一看的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')
据Tail recursion定义版本尾部的quicksort
最后一个方法调用本身,这就是尾递归。但其他一些实现不是尾递归。
quicksort(left) + pivot + quicksort(right)
由于quicksort
的最终行动是sorted_left + pivot + sorted_right
其他人可以证实这一点的准确性吗? – 2013-06-20 16:39:55
- 1. 快速排序算法(递归)
- 2. 没有尾递归的快速排序
- 3. 为什么快速排序被认为是最快的排序算法?
- 4. 快速排序递归
- 5. 快速排序python递归
- 6. 快速排序和设置在递归版本我有我的快速排序算法递归
- 7. 快速排序算法行为奇怪
- 8. 这个递归快速排序程序为什么不起作用?
- 9. 如何实现尾递归快速排序在斯卡拉
- 10. 为什么冒泡排序比快速排序快
- 11. 尾递归算法归并
- 12. 什么是最快的快速排序 - 排序算法的排名表?
- 13. 蟒蛇快速排序递归
- 14. Python的快速排序递归深度
- 15. JMH微基准递归快速排序
- 16. 非递归的快速排序在RCPP
- 17. 这个尾巴为什么递归?
- 18. 为什么不是这种尾递归?
- 19. 为什么尾递归优化比Python中的正常递归更快?
- 20. 为什么Array.map比尾递归映射更快(相当)?
- 21. 为什么我的Scala尾递归比while循环更快?
- 22. 为什么这个快速排序不排序
- 23. 这用什么分区算法? (用于快速排序)
- 24. 合并中的递归排序,快速排序和树遍历
- 25. 尾递归归并排序OCaml中
- 26. 以第一个元素为快速排序的快速排序
- 27. 在F#/ OCaML中实现尾部递归版本的类快速排序功能
- 28. 迭代(基于堆栈)快速排序比递归更快吗?
- 29. 为什么Javascript的Bubble排序比其他排序算法快得多?
- 30. 为快速排序算法获取错误的输出
你看了,从你前面的问题维基百科的文章? – Andrey 2012-08-08 11:59:58
@Andrey是的,我做了,但我发现了我所联系的答案更容易理解。的 – Geek 2012-08-08 12:04:14
可能重复[什么是尾递归?(http://stackoverflow.com/questions/33923/what-is-tail-recursion)。一旦你看到尾递归,该算法的定义的定义在17点28分,很显然,这是尾递归,因为递归步骤的返回值是对自身的调用的返回值。 – 2015-02-28 10:25:28