antirez weblog

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.

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): 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: 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

• La ricorsione secondo wikipedia
• Alcune slide sulla ricorsione e su come funziona praticamente una chiamata ricorsiva in molti linguaggi
• Il prossimo articolo di questo blog