Comments for post Le basi della ricorsione, seconda parte
Navigatore Anonimo writes:
Domenico writes: Chiedo venia, è passato un po' di tempo e ho finito per confondermi con i termini.
In effetti: "Si parla di ricorsione di coda quando la chiamata ricorsiva è l'ultima istruzione eseguita nella funzione. Questo tipo di algoritmo ricorsivo è possibile trasformarlo semplicemente in una versione iterativa, che di solito è più efficiente, in quanto non occorre mantenere lo stato della funzione una volta calcolata come è stato fatto nell'esempio precedente. Se l'algoritmo non è ricorsivo di coda, per trasformarlo in una versione iterativa occorre utilizzare un meccanismo di mantenimento dello stato analogo a quello che è utilizzato implicitamente nelle chiamate di funzione." [tratto da wikipedia]
Io invece mi riferivo al fatto che implementando una lista occorre gestire il caso di lista vuota e di ultimo elemento della lista (cioè un elemento seguito da una lista vuota).
Non mi aveva mai convinto questo approccio e avevo trovato più naturale effettuare chiamate al puntatore della lista. In questo modo bastava testare all'interno della funzione se fossimo di fronte ad una lista vuota... spero di essermi spiegato, se li ritrovo e interessa posto il codice in questione :-)
antirez writes: @Domenico: si Domenico, molti problemi per essere espressi in termini di ricorsione di coda diventano meno naturali da leggere e scrivere purtroppo. Con la pratica si finisce per farci l'abitudine e si diventa abbastanza bravi a trasformare la ricorsione in ricorsione di coda quando e' necessario.
Per fortuna un caso notevole di ricorsione di coda e' abbastanza naturale senza la necessita' di alcuna trasformazione: e' il caso degli automi a stati finiti in cui la chiamata alla prossima funzione (che rappresenta il prossimo stato) e' sempre in coda.
Domenico writes: Hai citato in questo articolo la ricorsione di coda, che per molti risulta più semplice ed esiste un algoritmo (se ben ricordo) per passare da una struttura iterativa ad una ricorsiva di coda, cosa che implica quanto meno l'idem potenza della ricorsione con l'iterazione.
Tuttavia quando mi approccia alla ricorsione, trovai più naturale ragionare in termini di ricorsione di testa; sviluppandola in C, con a disposizione i puntatori, si risolvevano i problemi di lista vuota (da gestire a parte o con il solito dummy) senza dover fare casi e in pratica mi sembrava di avere una struttura più regolare; mi chiedevo se anche a te è capitata la stessa cosa.
antirez writes: @neon: ottima soluzione! Hai risolto il sotto-problema in maniera imperativa, ma cosa importa? Il problema che si prestava alla risoluzione ricorsiva e' quello esterno, dunque hai scritto una bella funzione. Nell'articolo ho mostrato il sotto problema in maniera ricorsiva perche' mi sembrava un caso interessante e non molto intuitivo senza fare un po' di sforzo.
neon writes: Ho provato a risolvere l'ordinamento in un'unica funzione.
function sortlist($l)
{
if (count($l) < 2) return $l;
$m = min($l);
array_splice($l, array_search($m, $l), 1);
return array_merge(array($m), sortlist($l));
}
E' corretta?
Forse non è puramente ricorsiva perchè uso la variabile $m e quindi non posso scriverla in forma unicamente funzionale. Modifico anche la lista e non credo sia una buona cosa.
home