Le basi della ricorsione

Thursday, 19 April 07
Una immagine ricorsiva La ricorsione e' un concetto fondamentale della programmazione: appropriarsene e padroneggiarla e' una delle cose che fanno la differenza, ad un tratto molti problemi che con un algoritmo iterativo sembrano essere difficili da trattare diventano banali. E' il primo gradino di una progressione di astrazioni da imparare che includono le funzioni come oggetti di prima classe, le chiusure, le continuazioni, la metaprogrammazione, la programmazione parallela ed altre ancora, ma forse uno dei piu' importanti.

Cos'e' la ricorsione?

Sembra una domanda banale solo perche' ha una risposta banale: La ricorsione e' una tecnica di programmazione in cui una funzione chiama se stessa.
In realta' questa definizione ci dice ben poco sulla vera natura della ricorsione, parla solo del modo in cui essa viene messa in opera. La ricorsione ha molto piu' a che fare con l'idea di esprimere un problema in termini di se stesso.


Esprimendo i problemi in termini di se stessi a volte si scopre che bisogna risolverli solo nel caso piu' banale, perche' la formulazione stessa del problema e' la sua soluzione!.

Le cose viste in un modo diverso

La ricorsione e' piu' adatta ad alcuni tipi di problemi, ma per iniziare a comprenderla non c'e' niente di meglio che utilizzarla per risolvere problemi banali che sappiamo risolvere in altre maniere senza neppure pensarci.

Scrivere una funzione che conta da 5 a 12 ad esempio, e' qualcosa che tutti riusciamo a fare. In PHP verrebbe qualcosa come:
function itercount($start,$stop) {
    for($i = $start; $i <= $stop; $i++)
        echo("$i<br/>\n");
}
itercount(5,12);
Come potremmo risolevere lo stesso problema se for non esistesse utilizzando la ricorsione?. (Prima di guardare il codice che segue provate a farlo voi, non potete utilizzare for, while e nessun altro tipo di costrutto preesistente nel linguaggio). La soluzione e' la seguente funzione ricorsiva:
function countrec($start,$stop) {
    echo($start."<br/>\n");
    if ($start<$end)
        countrec($start+1,$stop);
}
countrec(5,12);
A prima vista countrec puo' sembrare un modo complicato di risolvere il problema rispetto alla soluzione iterativa, ma se guardiamo bene la semplicita' della soluzione iterativa e' data dal fatto che for e' uno strumento specializzato per contare: nonostante la versione ricorsiva ne faccia a meno la differenza di lunghezza tra le due funzioni e' solo una riga di codice.

Se invece di concentrarci sulla lunghezza analizziamo la complessita' intrinseca delle due funzioni, notiamo che per spiegare la prima funzione a chi non capisce niente di programmazione bisognerebbe spiegare il funziona for: gli incrementi, i test, l'inizializzazione, e poi il concetto di variabile (che e' diverso da quello di parametro di una funzione che chi non programma ma ha un minimo di infarinatura in matematica potrebbe gia' conoscere).

La funzione ricorsiva invece non utilizza variabili se non come parametri della funzione (volendo potrebbero essere immutabili e funzionerebbe lo stesso), non incrementa nulla, non usa un costrutto esterno, c'e' solo una condizionale, una somma, e una chiamata a se stessa.

Questo non vuol dire che dovremmo scrivere i cicli in maniera ricorsiva anche quando non c'e' alcun vantaggio quando programmiamo in un linguaggio imperativo come il PHP, ma questo esempio indica che in generale l'idea di ciclo che e' intuitivamente cosi' iterativa puo' essere espressa in maniera alternativa utilizzando la ricorsione.

Proviamo ora con un problema piu' complesso. Vogliamo scrivere una funzione che dato un array trovi l'elemento piu' grande. Anche in questo caso il problema e' semplice da risolevere iterativamente:
function maxval($l) {
    $max = $l[0];
    for($i = 1; $i < count($l); $i++)
        if ($l[$i] > $max) $max = $l[$i];
}
Siamo talmente abituati a risolvere i problemi in maniera iterativa che ci sembra normale avere un indice, una variabile in cui memorizziamo il valore massimo trovato fino a quel punto e che aggiorniamo se ne troviamo uno ancora maggiore. Eppure questo problema si offre gia' ad una risoluzione che utilizza il fatto che puo' essere enunciato in termini di se stesso.

Infatti potremmo dire (utilizzando il termine lista e array in maniera intercambiabile):
Il valore massimo di una lista e' il massimo tra il suo primo elemento e il valore massimo della restante lista.
Che tradotto in codice diventa:
function maxval($l) {
    if (count($l) == 1) return $l[0];
    return max(first($l),maxval(rest($l)));
}
Le funzioni first e rest saranno piu' o meno le seguenti, e sono utili in molti programmi che riguardano la definizione in termini ricorsivi di problemi che hanno a che fare con le liste (che in realta' in PHP sono array).
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); }
Questo codice ha una proprieta' interessante, si puo' quasi leggere come se fosse la definizione del problema. Nessuno definirebbe il problema in maniera naturale in termini iterativi, ve lo immaginate dire qualcosa come:
Il valore massimo di una lista e' il valore che si ottiene inizializzando una variabile al valore del primo elemento della lista e aggiornando tale valore ogni qual volta un elemento successivo della lista ha un valore maggiore di quello attualmente contenuto nella variabile.
Suona decisamente peggio.

E' fondamentale notare che nella soluzione ricorsiva abbiamo dovuto risolvere in maniera diretta il problema solo nel caso in cui la lista contiene un singolo elemento! E in tal caso ovviamente il massimo valore della lista e' l'unico elemento che essa possiede.

Nel prossimo post il seguito della storia, con le soluzioni agli esercizi proposti di seguito.

Esercizi per gli smanettoni

Provate a risolevere i seguenti problemi in termini ricorsivi:
  • Scrivere una funzione ricorsiva iseven($x) che ritorna true se x e' pari, altrimenti false.
  • Scrivere una funzione ricorsiva printlist($l) che stampa il contenuto di una lista.
  • Scrivere una funzione ricorsiva sortlist($l) che ordina una lista di numeri formulando il problema dell'ordinamento in termini di se stesso. Non bisogna usare quicksort, mergesort o altri algoritmi complessi, basta pensare al problema dell'ordinamento dal punto di vista piu' semplice possibile per trovare un programma che risolve il problema in maniera banale, esattamente come abbiamo visto per il problema del numero piu' grande di una lista.


Leggi la seconda parte dell'articolo.

Per approfondire

14401 views*
Posted at 08:14:35 | permalink | 20 comments | print
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.

Comments

Fra_T writes:
19 Apr 07, 10:31:44
Sono in difficoltà con il terzo problema :D

I primi due:

function iseven($x){
if($x == 0) return true;

if( ($x -= 2) <= 1 )
if($x) return false;
else return true;
return iseven($x);
}
function printlist($a){
if($a)
echo array_shift($a), printlist($a);
}
antirez writes:
19 Apr 07, 10:43:49
Ciao Fra_T: sei sulla buona strada con tutti e due i problemi ma in relata' le due soluzioni modificano delle variabili direttamente per cui si perde l'idea di descrizione del problema in termini di se stesso almeno in parte. Prova ad evitare array_shift e $x -= 2. Il secondo e' quasi perfetto dopo questa modifica mentre il primo (iseven) puo' essere semplificato in maniera massiccia.
Fra_T writes:
19 Apr 07, 11:01:15
Il 2° così può andare?

function printlist($a){
if($a)
echo $a[0], printlist(array_slice($a, 1));
}

Il primo lo farei così, ma non c'è ricorsione :D

function iseven($x){
if($x%2)
return false;
return true;
}
antirez writes:
19 Apr 07, 11:11:00
@Fra_T: il secondo e' OK, il primo non e' ricorsivo :)
Un problema del secondo pero' e' che in realta' la echo dovrebbe essere estratta dalla ricorsione (basta mettere punto e virgola invece della virgola in pratica). C'e' un motivo preciso che si chiama tail recursion optimization per fare questo, e anche il fatto che in realta' il valore di ritorno non viene utilizzato.
Fra_T writes:
19 Apr 07, 12:19:28
ah, grazie dell'info... ma veniamo alla prima :D Così?

function iseven($x){
if($x == 0) return true;
if($x == 1) return false;
return iseven($x-2);
}
Fra_T writes:
19 Apr 07, 14:29:47
Il massimo o cui sono arrivato per il terzo problema è questa funzione:

function sortlist($a) {
if(count($a) == 0) return array();
return array_merge(
(array) min($a),
sortlist(
array_diff(
$a, array( min($a) )
)
)
);
}

Solo che elimina dall'array ritornata i numero doppi... aspetterò le soluzioni :D
antirez writes:
19 Apr 07, 16:21:51
Fra_T: anche in questo caso ci sei andato veramente vicino, dal punto di vista logico la soluzione e' completamente accettabile perche' il problema e' espresso e risolto in termini ricorsivi, l'imperfezione e' nella implementazione che usa invece merge + diff. Complimenti comunque :) Al prossimo post con le soluzioni.
Paolo writes:
19 Apr 07, 20:20:17
Pero' tieni presente che scrivendo programmi in maniera' ricorsiva si puo' perdere molto in efficienza per mettere e togliere molti record nella stack ecc. :-) Molti programmatori ricorrono alla ricorsione solo quando non riescono a risolvere il problema in altro modo, e comunque anche in questo caso si puo' scrivere l'equivalente non ricorsivo di una funzione ricorsiva simulando la stack. Comunque si perde sempre in efficienza
antirez writes:
19 Apr 07, 20:22:38
@Paolo: ciao Paolo... surprise, questo e' vero solo con i linguaggi scarsi come PHP & company ;) In quelli buoni c'e' un concetto che si chiama "tail recursion optimization" che elimina tale problema, dal punto di vista dello spazio il programma rimane asintoticamente identico a quello iterativo. Ne parlero' di certo in un prossimo articolo.
Fabrizio writes:
19 Apr 07, 22:13:08
non entro nel tecnicismo ma voglio segnalare la mia stima per questi post! Un grande! :)

Senza considerare che molti dei tuoi suggerimenti poi li applico. Penso ad esempio alla funzione memoize.
antirez writes:
19 Apr 07, 23:23:45
Fabrizio: grazie mille! sei troppo buono. Riguardo a memoize mi sa che ho una versione piu' veloce e performante in cantiere :) Ci ho pensato l'altro giorno e ho dimenticato di implementarla ma ora che me ne sono ricordato grazie a te la segno nella TODO list.
neon writes:
20 Apr 07, 09:19:50
La funzione iseven() finale di Fra_T contiene un check in più.

function iseven($x)
{
if($x == 0) return true;
return !iseven($x-1);
}

La seconda l'ho fatta praticamente allo stesso modo, aggiungendo solo il controllo di array vuoto.

La cosa strana è che la terza l'ho fatta anche uguale alla sua... basandomi unicamente sul tuo esempio con maxval().

(c'è un errore nel primo esempio s/end/stop/)

Se ho tempo ci ragiono ancora su, volevo risolverla prima dei tuoi risultati :P
antirez writes:
20 Apr 07, 09:44:53
@neon: Ottimo per iseven! Un numero e' pari se il suo precedente non lo e' :) anche se io avrei scritto if ($x == 1) return false. E' esattamente identico ma mi sembra piu' matematicamente corretto.

Non e' strano che la funzione di ordinamento somiglia a quella di Fra_T! Anche io ho usato la stessa logica, e' il modo naturale di esprimere tramita la ricorsione un sacco di problemi, e' anche un po' come faresti a mano. Prendi l'elemento piu' grande e lo metti a sinistra. Poi cerchi quello piu' grande tra i rimanenti e lo metti subito dopo, e cosi' via :)
Fra_T writes:
20 Apr 07, 10:12:20
iseven!! non ci avevo pensato così... bella soluzione :)
neon writes:
20 Apr 07, 10:56:42
Ecco adesso credo di esserci vicino, non conoscevo la funzione array_search() per trovare la key del valore min (o max).

Al momento sono arrivato a trovare questa soluzione: cerco il valore min nell'array, se è diverso dal primo li scambio e poi continuo con il resto dell'array senza il primo valore. In questo modo non dovrebbero esserci problemi neanche con i valori ripetuti. Gli ultimi problemi li ho a farmi ritornare l'array dalla funzione ma ormai ci sono quasi ;)
antirez writes:
20 Apr 07, 11:05:02
@FraT: @neon: il problema dell'ordinamento lo risolvete meglio se lo scomponete in due sottoproblemi diversi, il primo dei quali e': scrivere una funzione ricorsiva che dato una lista in input restituisce in output il suo elemento minore e il resto della lista.

Nel fine settimana comunque arrivano le soluzioni :)
Fra_T writes:
20 Apr 07, 12:21:22
>> Gli ultimi problemi li ho a
>> farmi ritornare l'array dalla
>> funzione ma ormai ci sono quasi ;)

Per lo stesso problema o usato array_merge... ci sarà una soluzione migliore, ma non la conosco :D
Jack writes:
21 Apr 07, 10:53:10
Confermo sulla tail recursion! Anche in C esiste, e in pratica attraverso tale tecnica di programmazione si elimina il bisogno di aprire mille stack di attivazione. In sostanza è un programma ricorsivo con l'efficienza di un programma iterativo.
Gin_Phreaks writes:
27 Nov 08, 14:36:49
un buon esempio e articolo sulla ricorsione:
http://www.autistici.org/ermes/index.php?pag=1&...;post=25
Sabrina writes:
10 Apr 09, 10:09:18
ciao!
io nei prossimi mesi dovrò sostenere l'esame di algoritmi e strutture dati, incentrato in particolare sulla ricorsione.
ho un dubbio.
molti miei colleghi applicano la ricorsione in modo meccananico senza comprendere veramente come funzione l'algoritmo proposto. cioè applicano le regole.
io invece perdo prima un pò di tempo a cercare di capire come funzione il tutto senza ricorsione e poi la applico.
secondo voi applicare solo le regole base può bastare?
e se si, potreste farmi degli esempi macro a cui si può ricondurre ogni esercizio?
grazie enormemente.
comments closed