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:

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

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. 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. 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

• Documento PDF sulla ricorsione a cura della professoressa Emanuela Fachini
• Ricorsione di coda
• Structure and Interpretation of Computer Programs