Qual è il vantaggio dell'utilizzo di ricorsività qui?

Question 1

Una chiamata di funzione ricorsiva della coda consente al compilatore di eseguire un'ottimizzazione speciale che normalmente non può con una ricorsione regolare. In una funzione ricorsiva della coda, la chiamata ricorsiva è l'ultima cosa da eseguire. In questo caso, invece di allocare un frame dello stack per ogni chiamata, il compilatore può rielaborare il codice per riutilizzare semplicemente l'attuale frame dello stack, il che significa che una funzione di registro della coda utilizzerà solo un singolo frame stack rispetto a centinaia o addirittura migliaia.

Questa ottimizzazione è possibile perché il compilatore sa che una volta effettuata la chiamata ricorsiva della coda, non saranno necessarie copie precedenti di variabili, perché non c'è più codice da eseguire. Se, ad esempio, un'istruzione di stampa seguisse una chiamata ricorsiva, il compilatore avrebbe bisogno di conoscere il valore della variabile da stampare dopo il ritorno della chiamata ricorsiva e quindi il frame dello stack non può essere riutilizzato.

Ecco la pagina wiki se desideri maggiori informazioni su come funziona questo "salvamento dello spazio" e stack in realtà, insieme ad esempi: Chiamata di coda

EDIT: non ho spiegato come questo vale per QuickSort, vero? Bene, alcuni termini vengono lanciati in quell'articolo che rendono tutto confuso (e in parte è semplicemente sbagliato). La prima funzione data (QuickSort) fa una chiamata ricorsiva a sinistra, una chiamata ricorsiva a destra e quindi esce. Si noti che la chiamata ricorsiva a destra è l'ultima cosa che accade nella funzione. Se il compilatore supporta l'ottimizzazione ricorsiva della coda (spiegata sopra), solo le chiamate di sinistra creano nuovi fotogrammi di stack; Tutte le chiamate giuste riutilizzano il frame corrente. Questo può salvare alcuni Frame in pila, ma può ancora soffrire del caso in cui il partizionamento crea una sequenza di chiamate in cui l'ottimizzazione della ricorsione della coda non ha importanza. Inoltre, anche se le chiamate sul lato destro usano lo stesso frame, le chiamate sul lato sinistro chiamate entro Le chiamate sul lato destro usano ancora lo stack. Nel peggiore dei casi, la profondità dello stack è N.

La seconda versione descritta è non Un QuickSort ricorsivo coda, ma piuttosto un QuickSort in cui solo l'ordinamento a sinistra viene eseguito in modo ricorsivo e l'ordinamento giusto viene eseguito usando il ciclo. In effetti, questo QuickSort (come precedentemente descritto da un altro utente) non può avere l'ottimizzazione della ricorsione della coda applicata ad esso, perché la chiamata ricorsiva non è l'ultima cosa da eseguire. Come funziona? Se implementata correttamente, la prima chiamata a QuickSort è la stessa di una chiamata sul lato sinistro nell'algoritmo originale. Tuttavia, non vengono chiamate chiamate ricorsive sul lato destro. Come funziona? Bene, il ciclo si occupa di questo: invece di ordinare "a sinistra quindi a destra", ordina la sinistra con una chiamata, quindi ordina la destra ordinando continuamente solo il sinistra della destra. È davvero ridicolo, ma fondamentalmente è solo ordinare così tanti sinistre che i diritti diventano elementi singoli e non devono essere ordinati. Ciò rimuove efficacemente la giusta ricorsione, rendendo la funzione meno ricorsiva (pseudo ricorsivo, se vuoi). Tuttavia, la vera implementazione non sceglie ogni volta solo il lato sinistro; Sceglie il lato più piccolo. L'idea è sempre la stessa; Fondamentalmente fa solo una chiamata ricorsiva da un lato anziché entrambi. Scegliere il lato più corto assicurerà che la profondità dello stack non possa mai essere più grande di Log2 (N), che è la profondità di un albero binario adeguato. Questo perché il lato più corto sarà sempre al massimo delle dimensioni della nostra sezione di array attuale. L'implementazione fornita dall'articolo non garantisce tuttavia, perché può soffrire dello stesso scenario peggiore di "Left is the Whole Tree". Questo articolo in realtà ne dà una buona spiegazione se sei disposto a fare più lettura: Selezione efficiente e smistamento parziale basato su QuickSort

Question 2

Il vantaggio, l'intero punto della versione "ricorsiva/iterativa mista", cioè la versione che elabora un sotto-range per ricorsione e un'altra sotto-range per iterazione, è che scegliendo quale delle due sottosegre garantire che la profondità della ricorsione non supererà mai log2 N, indipendentemente da quanto sia cattiva la scelta del perno.

Per il TAIL-RECURSIVE-QUICKSORT Pseudocodice fornito nella domanda, in cui l'elaborazione ricorsiva viene eseguita per prima da una chiamata ricorsiva letterale, che la chiamata ricorsiva dovrebbe essere data il più corto sotto-range. Che di per sé si assicurerà che la profondità di ricorsione sarà limitata da log2 N. Pertanto, al fine di raggiungere la profondità di ricorsione, garantire il codice deve assolutamente confrontare le lunghezze dei secondari prima di decidere quale sotto-range elabora mediante chiamata ricorsiva.

Una corretta implementazione di questo approccio potrebbe sembrare seguente (prendendo in prestito lo pseudocodice come punto di partenza)

HALF-RECURSIVE-QUICKSORT(A, p, r)
   while p < r
      q = PARTITION(A, p, r)
      if (q - p < r - q)
        HALF-RECURSIVE-QUICKSORT(A, p, q-1)
        p = q+1
      else
        HALF-RECURSIVE-QUICKSORT(A, q+1, r)
        r = q-1

Il TAIL-RECURSIVE-QUICKSORT Lo pseudocodice che hai fornito non fa alcun tentativo di confrontare le lunghezze dei secondari. In tal caso, non fornisce alcun vantaggio. E no, non è davvero "coda ricorsiva". QuickSort non può essere ridotto a un algoritmo di registro coda.

Se esegui una ricerca su Google sui termini "Qsort Loguy Higuy", troverai facilmente numerose istanze di un'altra popolare implementazione di QuickSort (stile di biblioteca standard C in base alla stessa idea di usare la ricorsione solo per una delle due sotto-ranghi . Tale implementazione per piattaforme a 32 bit utilizza uno stack esplicito di profondità massima di ~ 32 in particolare perché può garantire che la profondità di ricorsione non sarà mai più alta di quella. (Allo stesso modo, le piattaforme a 64 bit avranno bisogno solo della profondità dello stack di ~ 64.)

Il QUICKSORT La versione che effettua due chiamate ricorsive letterali è significativamente peggio N Nel peggiore dei casi. Con due chiamate ricorsive non puoi garantire che la profondità di ricorsione sarà limitata da log2 N. Un compilatore intelligente potrebbe essere in grado di sostituire la chiamata finale a QUICKSORT Con iterazione, cioè girare il tuo QUICKSORT nel tuo TAIL-RECURSIVE-QUICKSORT, ma non sarà abbastanza intelligente da eseguire il confronto della lunghezza del sotto-range.

Question 3

Vantaggio dell'utilizzo della recursione della coda: = in modo che il compilatore ottimizza il codice e lo converti in un codice non riceutivo.

Vantaggio del codice non registrato rispetto a uno ricorsivo: = Il codice non recursivo richiede meno memoria da eseguire rispetto a uno ricorsivo. Ciò è dovuto a cornici di stack inattiva che la ricorsione consuma.

Ecco la parte interessante:- Anche se i compilatori Potere La teoritica esegue quell'ottimizzazione, in pratica non lo fanno. Anche i compilatori diffusi come Dot-Net e Java non eseguono tale ottimizzazione.

Un problema che tutte le ottimizzazioni del codice devono affrontare è il sacrificio nell'abilità di debug. Il codice ottimizzato non corrisponde più al codice sorgente, quindi le tracce di stack e i dettagli delle eccezioni non possono essere facilmente compresi. Il codice ad alte prestazioni o le applicazioni scientifiche sono una cosa, ma per la maggior parte delle applicazioni dei consumatori è richiesto anche dopo il rilascio. Quindi le ottimizzazioni non vengono eseguite vigorosamente.

perfavore guarda:

Question 4

Sembra che ci sia un po ' di lessico confusione qui.

La prima versione è il tail-ricorsiva, perché l'ultima affermazione è una chiamata ricorsiva:

QUICKSORT(A, p, r)
  q = PARTITION(A, p, r)
  QUICKSORT(A, p, q-1)
  QUICKSORT(A, q+1, r)

Se si applica il tail-recursion di ottimizzazione, che è quello di convertire la ricorsione in un ciclo, si ottiene la seconda, che non è più tail-ricorsiva:

TAIL-RECURSIVE-QUICKSORT(A, p, r)
  while p < r
    q = PARTITION(A, p, r)
    TAIL-RECURSIVE-QUICKSORT(A, p, q-1)
    p = q+1

Il vantaggio di questo è che di solito, avrete bisogno di meno stack di memoria.Perché è che?Per capire, immaginare che si desidera ordinare un array con 31 elementi.Nell'improbabile caso che tutte le partizioni sono perfetti, cioèsi dividono la matrice di destra nel mezzo, la tua profondità di ricorsione sarebbe 4.Infatti, la prima divisione sarebbe resa di due partizioni di 15 articoli, il secondo dei due partizioni di 7 elementi, la terza due di 3 elementi, e dopo il quarto tutto è ordinato.

Ma le partizioni sono raramente questo perfetto.Come risultato, non tutte le ricorsioni andare altrettanto profonda.Nel nostro esempio, si potrebbe avere alcuni che sono solo tre livelli di profondità, e alcuni che sono 7 o più (caso peggiore è 30).Eliminando la metà delle ricorsioni, avete una buona probabilità che la vostra massima profondità di ricorsione sarà di meno.

Come AndreyT sottolineato, spesso i valori sono confrontati per assicurarsi che la partizione più grande è sempre trattati in modo iterativo, e il più piccolo in modo ricorsivo.Che garantisce il più possibile la profondità di ricorsione per un dato input e pivot strategia di selezione.

Ma questo non è sempre il caso.A volte, la gente vuole ottenere risultati il più presto possibile, o desidera trovare e ordinare solo i primi n elementi.In questi casi hanno sempre voglia di ordinare la prima partizione prima che la seconda.Anche in questa situazione, eliminando la ricorsività di solito migliora l'utilizzo della memoria, e non fa che peggiorare le cose.

Question 5

Non so esattamente se questo è il posto corretto per fare questo dubbio o avrei dovuto pubblicare una nuova domanda, ma ho un dubbio abbastanza simile.



void print(int n) {
  if (n < 0) return;
  cout << " " << n;
// The last executed statement is recursive call
  print(n-1);
  print(n-1);
}

Questa coda è ricorsiva?

Question 6

La ricorsione di coda è l'ottimizzazione effettuata dai moderni compilatori chiamati eliminazione della chiamata di coda. Quando la funzione chiamante/genitore non deve fare nulla nelle fasi di svolgimento dopo che le chiamate del bambino hanno terminato, l'ultima cosa è la stessa chiamata di ricorsione, quindi il compilatore moderno usa GOTO e etichette per l'ottimizzazione.

Esempio: la nostra versione -> stampa da n a 1

void fun(int n){
if(n==0)
return;
printf("%d\n",n);
fun(n-1)
}

Dopo l'ottimizzazione->

void fun(int n){
start:
if(n==0)
return;
printf("%d\n",n);
n=n-1;
goto start;
}

Vantaggi di questa ottimizzazione: 1. Uso pochissimi frame dello stack per chiamate di registro di coda 2. Consumi in meno memoria 3.Non deve essere necessario salvare il record di attivazione della procedura, questo riduce il sovraccarico della funzione. 3. Non più guasto di segmentazione è C/C ++ e lo stack di Overflow in Java.