Le basi della ricorsione, seconda parte
Saturday, 21 April 07
Qualche giorno fa il post sulle basi della ricorsione
aveva lasciato alcuni quesiti aperti, e aveva stimolato altri interrogativi all'interno dei commenti. Iniziamo subito prendendo in esame gli esercizi proposti
nel precedente articolo che alcuni dei lettori di questo blog hanno risolto mostrando di essere entrati nella logica del pensiero ricorsivo.
Pari e dispari
Il modo piu' diretto di esprimere il problema della parita' di un numero in termini ricorsivi e' il seguente:
Un numero e' pari se il suo precedente e' dispari
che tradotto in codice diventa:
function iseven($n) {
if ($n == 1) return false;
return !iseven($n-1);
}
La seconda riga della funzione e' la traduzione in codice della definizione precedente, la prima riga invece risolve, come e' sempre necessario fare, il problema nel caso base, altrimenti si creerebbe una ricorsione infinita e il programma non terminerebbe mai. Infatti nella pratica e' ancor meglio enunciare il problema comprendendo il caso base:
Uno e' dispari.
Un numero e' pari se il suo precedente e' dispari.
Ora la definizione e' esattamente identica alla sua implementazione.
E' come se la funzione iseven non risolvesse il problema in maniera
diretta, ma lo risolvesse come effetto collaterale del fatto che ne e' una descrizione.
Ordinamento
Nel caso dell'ordinamento di una lista di numeri il problema si puo' enunciare il termini ricorsivi in maniera simile a quanto accadeva per il problema della ricerca dell'elemento massimo di una lista:
Una lista di un solo elemento o vuota e' ordinata.
La versione ordinata di una lista si ottiene concatenando il suo elemento minore con la versione ordinata della lista rimanente.
Anche questa volta il caso base e' stato incluso nella definizione
direttamente. Se si osserva bene questo problema si nota che ne include
uno piu' piccolo: serve avere una funzione che separi una lista in due
parti: il suo elemento minore dal resto della lista.
La versione ordinata di una lista si ottiene concatenando il suo elemento minore con la versione ordinata della lista rimanente.
Per semplificare ci basta una funzione che data una lista ritorna la stessa lista che ha pero' il suo elemento minore spostato in posizione iniziale. Potremmo esprimere questo sotto problema nel seguente modo, chiamando l'output lista semi ordinata per semplicita' di linguaggio.
Una lista vuota o di un solo elemento e' semi ordinata.
Una lista semi ordinata si ottiene concatenando il suo primo elemento E
alla destra della lista subordinata rimanente S se E e' maggiore a S[0],
altrimenti concatenandolo a sinistra.
In pratica se ho la lista (4 9 2 6 5) separo il primo elemento
dal resto ottenendo 4 e (9 2 6 5). Chiamo ricorsivamente la
funzione per la semi ordinazione su questa lista rimanente e ottengo
S, poi concateno 4 + S se 4 e' minore o uguale al primo elemento di S ottenendo la lista (4 ... elementi di S ...), o
S + 4 se 4 e' maggiore al primo elemento di S, ottenendo la lista (... elementi di S ... 4).
Tradotto in codice otteniamo la seguente funzione:
function first($l) {
if (count($l) == 0) return false;
return $l[0];
}
function rest($l) {
if (count($l) == 0) return Array();
return array_slice($l,1);
}
function semisort($l) {
if (count($l) < 2)
return $l;
if (first($l) <= first(semisort(rest($l))))
return array_merge(Array(first($l)),semisort(rest($l)));
else
return array_merge(semisort(rest($l)),Array(first($l)));
}
Ancora una volta abbiamo bisogno delle nostre fide amiche first e rest incontrate nello scorso articolo. La funzione semisort puo' sembrare un po' complessa scritta in maniera puramente funzionale (non si usano variabili), per renderla un po' piu' chiara proviamo per un attimo ad introdurre una variabile temporanea:
function _semisort($l) {
if (count($l) < 2)
return $l;
$t = semisort(rest($l));
if ($l[0] <= $t[0])
return array_merge(Array($l[0]),$t);
else
return array_merge($t,Array($l[0]));
}
Ora dovrebbe essere molto chiaro.
E' l'equivalente di prendere dei
bastoncini di lunghezza diversa da un sacchetto uno dopo l'altro e
disporli su un tavolo mettendo a destra tutti quelli che sono piu'
lunghi del primo della fila, a sinistra quelli piu' corti del primo
(che diventano dunque i nuovi primi a loro volta).
Ora che abbiamo semisort scrivere la funzione che ordina una lista
diventa semplice utilizzando la precedente definizione.
function recsort($l) {
if (count($l) < 2) return $l;
return array_merge(first(semisort($l)),recsort(rest(semisort($l))));
}
Basta concatenare l'elemento minore della lista con la versione
ordinata del resto della lista e il gioco e' fatto (provare per credere,
il programma ordina correttamente la lista e gestisce ripetizioni
dello stesso elemento).
Per finire il problema della stampa di una lista era banalmente risolvibile con questa funzione:
function printlist($l) {
if (count($l) == 0) return;
echo(first($l)."<br/>");
printlist(rest($l));
}
Applicazioni pratiche
Vista cosi' la ricorsione puo' sembrare semplicemente un esercizio fine a se stesso, invece solo dopo aver preso confidenza con tale tecnica un sacco di problemi reali possono essere risolti in questo modo.Ad esempio questo codice fa parte di oknotizie:
function showNewsCommentsRec($newsid, $inreplyto, $lmargin, $lstep) {
$newsSecret = createSecureId($newsid,"news_id");
$comments=dbListNewsComments($newsid,$inreplyto,false);
foreach($comments as $row) {
$commentclass = ($inreplyto == -1) ? "comment" : "commentreply";
showNewsComment($lmargin,$lstep,$newsSecret,$row,$commentclass);
showNewsCommentsRec($newsid, $row['id'], $lmargin+$lstep, $lstep);
}
}
E serve a visualizzare i commenti che appartengono ad una data news in forma
di thread, dando il giusto margine e spostando a destra le risposte.
Per chiarezza si noti che se $inreplyto e' -1 il commento non e' risposta
di un diverso commento ma sta alla radice.
La versione non ricorsiva di questo codice sarebbe stata molto piu' complessa, aavrebbe necessitato di uno stack e piu' logica di controllo. Questo non e' un esempio isolato, mi capita molto spesso di scrivere funzioni ricorsive per implementare pezzi di applicazioni web. Basta spostarsi su campi in cui le strutture dati in gioco sono piu' complesse, ad esempio la scrittura di interpreti o compilatori, per vedere tanta ricorsione in uso. Ad esempio Picol e' un interprete ricorsivo.
Spero di ritornare sull'argomento prima o poi, con una piccola panoramica del problema della ricorsione di coda e la sua ottimizzazione e della trasformazione di un algoritmo ricorsivo in uno iterativo utilizzando la tecnica della ricorsione di coda e aggiungendo se necessario degli stack. Altri argomenti di interesse sono le funzioni mutualmente ricorsive, la creazione di macchine a stati finiti utilizzando funzioni mutualmente ricorsive ottimizzate tramite la eliminazione della ricorsione di coda e tanto altro.
Per approfondire
Do you like this article?
Subscribe to the RSS feed of this blog or use the newsletter service in order to receive a notification every time there is something of new to read here.
Note: you'll not see this box again if you are a usual reader.
Subscribe to the RSS feed of this blog or use the newsletter service in order to receive a notification every time there is something of new to read here.
Note: you'll not see this box again if you are a usual reader.
Comments
21 Apr 07, 08:04:19
@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.
22 Apr 07, 16:06:09
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.
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.
22 Apr 07, 16:18:05
@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.
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.
22 Apr 07, 16:38:10
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 :-)
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 :-)
02 Dec 09, 06:38:36
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.