Quando usare la ricorsione della coda?

Question

Quando usare la ricorsione della coda?

#1 da (10 voti)
#2 da (2 voti)

3

Recentemente sono entrato nella programmazione funzionale. Ho fatto una domanda qui sopra "'Memorizzare' i valori nella programmazione funzionale" e ho imparato un sacco di cose che non avevo nemmeno capito che volevo ancora imparare. È stato molto utile Mi ha lasciato alcune nuove domande senza risposta. Il primo di questi è, quando dovrei effettivamente ricorrere alla ricorsione in coda?

Nel mio esempio, l'ho usato inavvertitamente. Stavo usando una funzione di esempio per aumentare xey; x ^ y.

Ci sono due modi principali in cui ciò può essere fatto. Un modo ricorsivo non coda, come segue:

(il seguente è tutto codificato in pseudocodice)

f(x,y){
   if y > 1,
     return x * f(x,y-1);
   else
     return x;
}

Ma come alternativa alla ricorsione in coda, potrei farlo in questo modo:

f(x,y,z){
   if z == 'null',
     f(x,y,x);
   else if y > 1,
     f(x*z,y-1,z);
   else
     return x;
}

Entrambi funzionano bene, ma dal momento che il primo è ricorsivo non di coda, potrebbe teoricamente rimanere bloccato su operazioni particolarmente grandi. Tuttavia, anche se questo è il caso, farlo senza ricorsione di coda solo si sente più pulito. Non ho bisogno di usare un argomento in più, e il mio codice sembra molto "mistico". Dopo tutto, return x * f (x, y-1) è solo un altro modo per dire return x * x ^ y-1.

Immagino che cosa mi stia chiedendo, ci sono momenti in cui non dovrei usare la ricorsione della coda? Esiste un codice che è meglio lasciare senza ricorsione, o dovrei semplicemente prendere l'abitudine di ricorrere a tutte le funzioni quando applicabile?

functional-programming tail-call

posta Ucenna 22.09.2016 - 09:25

fonte

2 risposte

2

Dipende da quanto apprezzi l'elaborazione efficiente senza il rischio di overflow dello stack rispetto alla leggibilità. E anche se trovi ricorsione e accumulatori un po 'strani, perfettamente strani o perfettamente normali.

In altre parole, il trade-off riguarda le qualità soggettive, motivo per cui non esiste una risposta generalmente accettata. Nota anche che più usi una funzione, più naturale sarà la visualizzazione di tu , il che è ottimo per te che lavori con il tuo codice personale, ma potenzialmente peggio per gli altri che devono lavorare con esso.

risposta data 22.09.2016 - 09:30

fonte

Leggi altre domande sui tag functional-programming tail-call

Quali sono i vantaggi della moltiplicazione della matrice rispetto alle singole variabili (grafica)? Perché il codice include una chiamata a un database o a un DAL non definito come client?

score 10 · Accepted Answer

Prima di tutto, la ricorsione è una misura dell'ultima risorsa nella programmazione funzionale. Utilizzare le funzioni di ordine superiore se è possibile farlo in modo pulito. Non posso sottolinearlo abbastanza.

Detto questo, la situazione più comune per non utilizzare la ricorsione in coda è quando attraversi una struttura ad albero, le stesse situazioni che usi ricorsività in lingue imperative che non rimuovono le chiamate di coda. Questo perché le profondità dello stack sono limitate alla profondità dell'albero e le versioni ricorsive della coda di questi algoritmi sarebbero estremamente contorte.

Qualunque cosa utilizzi un ciclo imperativo per dovrebbe essere ricorsiva in coda: attraversando matrici, liste concatenate, intervalli di interi per i calcoli matematici, ecc.

L'eccezione è che se conosci la dimensione è limitata. Le funzioni non ricorsive alla coda sono molto più leggibili, quindi dovresti sfruttare questa leggibilità, ma preparati a difendere come sai che la dimensione è limitata nella revisione del codice.