Perché l'ordinamento rapido viene chiamato un algoritmo ricorsivo di coda?

Question

So che algoritmo ricorsivo di coda è come written out in this SO answer. Comunque sto passando attraverso questo video of quick sort algorithm from MIT e alle 18:30 secondi il professore dice che questo è un algoritmo ricorsivo di coda. Non riesco a collegare come questo è ricorsivo della coda. Non stiamo facendo calcoli in nessuna fase della ricorsione o siamo noi? Puoi spiegare perché questo è citato come un esempio di algoritmo ricorsivo di coda. Si prega di basare la risposta sulla premessa che io so che cos'è un algoritmo ricorsivo. La parte che non mi è chiara è perché è chiamata coda ricorsiva?

Answer 1

Il primo passaggio (i) della funzione ricorsiva è il partizionamento. E poi, come ultimo passaggio, si chiama la funzione ricorsiva sulle due partizioni.

Da wikipedia:

In informatica, una chiamata coda è una subroutine che accade all'interno di un altro procedimento come la sua azione finale; può produrre un valore di ritorno che viene immediatamente restituito dalla procedura di chiamata.

Answer 2

La ricorsione della coda non si basa sul calcolo in fasi. Riguarda "la ricorsione potrebbe essere valutata senza creare stack di chiamate". L'esempio dato da What is tail recursion? è un caso speciale di questo. Se si guarda l'esempio più a fondo, quello che si può trovare è che

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

1) per eseguire il codice di cui sopra con successo, è necessario costruire lo stack di chiamate. Ma,

def tailrecsum(x,running_total=0): 
    if x==0: 
    return running_total 
    else: 
    return tailrecsum(x-1,running_total+x) 

2) per eseguire il codice di cui sopra, non è necessario per costruire lo stack di chiamate a causa di running_total. Basta creare lo stack di chiamate per la "chiamata originale" e per la ricorsione, non è necessario creare stack di chiamate, perché lo stato richiesto per valutare questa funzione è memorizzato in running_total.

E, a proposito del quick-sort, penso che il professore probabilmente intendesse che l'ordinamento rapido potrebbe essere ottimizzato "usando" la codifica della coda. Per le due parti ramificate di qsort(), possiamo usare la ricorsione di coda su un lato che ha elementi più alti (in base alla posizione di rotazione).

Answer 3

Dai un'occhiata alla pagina wiki di Quicksort. Esiste una versione di coda ricorsiva

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') 

Secondo la definizione di Tail recursion, l'ultima chiamata al metodo di quicksort è di per sé, che è la ricorsione in coda. Ma alcune altre implementazioni non sono ricorsive.

quicksort(left) + pivot + quicksort(right) 

Poiché l'azione finale in quicksort è sorted_left + pivot + sorted_right