Cosè la ricorsione della coda?

La ricorsione in coda è un caso speciale di ricorsione in cui la funzione chiamante non esegue più calcoli dopo aver effettuato una chiamata ricorsiva. Ad esempio, la funzione

 int f(int x, int y) { if (y == 0) { return x; } return f(x*y, y-1); } 

è ricorsiva di coda (poiché listruzione finale è una chiamata ricorsiva) mentre questa funzione non è ricorsiva di coda:

 int g(int x) { if (x == 1) { return 1; } int y = g(x-1); return x*y; } 

poiché esegue alcuni calcoli dopo che è stata restituita la chiamata ricorsiva.

La ricorsione in coda è importante perché può essere implementata in modo più efficiente della ricorsione generale. Quando facciamo una normale chiamata ricorsiva, dobbiamo inserire lindirizzo di ritorno nello stack di chiamate e poi saltare alla funzione chiamata. Ciò significa che abbiamo bisogno di uno stack di chiamate la cui dimensione sia lineare nella profondità delle chiamate ricorsive. Quando abbiamo la ricorsione in coda sappiamo che non appena torniamo dalla chiamata ricorsiva “torneremo immediatamente anche noi, quindi possiamo saltare lintera catena di funzioni ricorsive che ritornano e tornare direttamente al chiamante originale. Ciò significa che non “Non è assolutamente necessario uno stack di chiamate per tutte le chiamate ricorsive e può implementare la chiamata finale come un semplice salto, che ci fa risparmiare spazio.

Commenti

• hai scritto ” Ciò significa che ‘ non abbiamo bisogno di uno stack di chiamate per tutte le chiamate ricorsive “. Lo stack di chiamate sarà sempre lì, solo che lindirizzo di ritorno non deve essere scritto nello stack di chiamate, giusto?
• Dipende in una certa misura dal tuo modello di calcolo 🙂 Ma sì, su un computer reale il lo stack di chiamate è ancora presente, ‘ non lo stiamo utilizzando.
• E se ‘ è la finale chiamata ma in for for loop. Quindi fai tutti i tuoi calcoli sopra ma alcuni di essi in un ciclo for come def recurse(x): if x < 0 return 1; for i in range 100{ (do calculations) recurse(x)}
• @ thed0ctor – questo ricorsivo non ‘ t terminate.

Detto semplicemente, la ricorsione in coda è una ricorsione in cui il compilatore potrebbe sostituire la chiamata ricorsiva con un comando “goto”, quindi la versione compilata non dovrà aumentare la profondità dello stack.

A volte la progettazione di una funzione ricorsiva in coda richiede la creazione di una funzione di supporto con parametri aggiuntivi.

Ad esempio, questa non è una funzione ricorsiva di coda:

int factorial(int x) { if (x > 0) { return x * factorial(x - 1); } return 1; } 

Ma questa è una funzione di coda funzione ricorsiva:

int factorial(int x) { return tailfactorial(x, 1); } int tailfactorial(int x, int multiplier) { if (x > 0) { return tailfactorial(x - 1, x * multiplier); } return multiplier; } 

perché il compilatore potrebbe riscrivere la funzione ricorsiva in una non ricorsiva, usando qualcosa di simile (uno pseudocodice):

int tailfactorial(int x, int multiplier) { start: if (x > 0) { multiplier = x * multiplier; x--; goto start; } return multiplier; } 

La regola per il compilatore è molto semplice: quando trovi “return thisfunction(newparameters);“, sostituiscilo con “

“. Ma questo può essere fatto solo se il valore restituito dalla chiamata ricorsiva viene restituito direttamente.

Se tutte le chiamate ricorsive in una funzione possono essere sostituite in questo modo, allora è una coda -funzione ricorsiva.

La mia risposta si basa sulla spiegazione fornita nel libro Struttura e interpretazione dei programmi per computer . Consiglio vivamente questo libro agli informatici.

Approccio A: processo ricorsivo lineare

(define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1))))) 

La forma del processo per Lapproccio A è simile al seguente:

(factorial 5) (* 5 (factorial 4)) (* 5 (* 4 (factorial 3))) (* 5 (* 4 (* 3 (factorial 2)))) (* 5 (* 4 (* 3 (* 2 (factorial 1))))) (* 5 (* 4 (* 3 (* 2 (* 1))))) (* 5 (* 4 (* 3 (* 2)))) (* 5 (* 4 (* 6))) (* 5 (* 24)) 120 

Approccio B: processo iterativo lineare

(define (factorial n) (fact-iter 1 1 n)) (define (fact-iter product counter max-count) (if (> counter max-count) product (fact-iter (* counter product) (+ counter 1) max-count))) 

La forma del processo per l Approccio B ha questo aspetto:

(factorial 5) (fact-iter 1 1 5) (fact-iter 1 2 5) (fact-iter 2 3 5) (fact-iter 6 4 5) (fact-iter 24 5 5) (fact-iter 120 6 5) 120 

Il processo iterativo lineare (approccio B) viene eseguito in uno spazio costante anche se il processo è una procedura ricorsiva. Va anche notato che in questo approccio un insieme di variabili definisce lo stato del processo in qualsiasi punto. {product, counter, max-count}. Questa è anche una tecnica con cui la ricorsione in coda consente lottimizzazione del compilatore.

Nellapproccio A ci sono più informazioni nascoste che linterprete mantiene, che è fondamentalmente la catena di operazioni differite.

Commenti

• ‘ t essere solo (1) invece di (* 1)?

Ricorsione in coda è una forma di ricorsione in cui le chiamate ricorsive sono le ultime istruzioni nella funzione (da cui proviene la parte di coda). Inoltre, la chiamata ricorsiva non deve essere composta con riferimenti a celle di memoria che memorizzano valori precedenti (riferimenti diversi da i parametri della funzione) In questo modo non ci preoccupiamo dei valori precedenti e uno stack frame è sufficiente per tutte le chiamate ricorsive; la ricorsione in coda è un modo per ottimizzare gli algoritmi ricorsivi. Laltro vantaggio / ottimizzazione è che esiste un modo semplice per trasformare un algoritmo ricorsivo di coda in uno equivalente che utilizza literazione invece della ricorsione. Quindi sì, lalgoritmo per quicksort è effettivamente ricorsivo di coda.

QUICKSORT(A, p, r) if(p < r) then q = PARTITION(A, p, r) QUICKSORT(A, p, q–1) QUICKSORT(A, q+1, r) 

Ecco la versione iterativa:

QUICKSORT(A) p = 0, r = len(A) - 1 while(p < r) q = PARTITION(A, p, r) r = q - 1 p = 0, r = len(A) - 1 while(p < r) q = PARTITION(A, p, r) p = q + 1