爲什麼快速排序稱爲尾遞歸算法？

我知道一個尾遞歸算法就是爲written out in this SO answer。不過，我正在通過這video of quick sort algorithm from MIT和18:30秒教授說，這是尾遞歸算法。我無法連接這是如何尾部遞歸。我們不是在遞歸的任何步驟進行計算，還是我們？你能解釋爲什麼這被引用作爲尾遞歸算法的一個例子。請根據您的答案，我知道什麼是遞歸算法。我不清楚的部分是爲什麼它被稱爲尾遞歸？爲什麼快速排序稱爲尾遞歸算法？

來源

2012-08-08 Geek

你看了，從你前面的問題維基百科的文章？ – 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

遞歸函數的第一步驟（S）爲分區。然後，作爲最後一步，您可以在兩個分區上調用遞歸函數。

維基百科：

在計算機科學中，尾部呼叫是一個子程序調用發生這種情況內的另一個程序作爲其最後行動;它可能會產生一個返回的值，然後立即由調用過程返回。

來源

2012-08-08 12:02:11

尾遞歸是不是在步計算。這是關於「遞歸可以在沒有構建調用堆棧的情況下進行評估」。 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（）的兩個分支部分，我們可以在具有較高項目的一側使用尾遞歸（基於樞軸位置）。

enter image description here

來源

2012-08-08 12:25:23 jaeyong

你可以把你的答案中的調用堆棧進一步解釋。對我來說，你似乎需要在這兩個過程中構建調用堆棧。 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

來源

2012-08-08 12:25:45 xiaowl

其他人可以證實這一點的準確性嗎？ – 2013-06-20 16:39:55

爲什麼快速排序稱爲尾遞歸算法？

回答

相關問題