La ricorsione è spesso vista come un'amenità o qualcosa di difficile da utilizzare, spesso anche perchè associata alla celeberrima frase "l'iterazione è umana, la ricorsione divina".
In realtà la cosa è più semplice di quanto si possa pensare. Un metodo, funzione, procedura, routine ricorsiva non è altro che un metodo che invoca se stesso. Cosa significa tutto ciò?
Di norma si è abituati ad avere una funzione Topolino(), che invoca una funzione Pluto(). Ad esempio:
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title></title>
</head>
<body>
<?php
function Pluto(){ $str = 'Bau Bau! Arf Arf!'
echo $str;
}
function Topolino(){ $str = 'Qui Pluto!<br>';
Pluto();
echo $str;
}
Topolino();
?>
</body>
</html>
Nell'esempio è invocata la funzione Topolino(), che invoca al suo interno Pluto().Per avere una idea più chiara della ricorsione bisogna sapere cosa accade quando s'invoca una funzione.
La mia prima funziona ricorsiva e le regole che dominano la ricorsione
Ora si immagini di scrivere una funzione CountDown($n) che invochi se stessa come nell'esempio seguente:
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title></title>
</head>
<body>
<?php
function CountDown($n){
echo "$n<br>";
CountDown($n-1);
}
CountDown(50);
?>
</body>
</html>
Cosa succede nello stack delle chiamate in questo caso?
Alla riga 14 è invocato il metodo CountDown(50), quindi è memorizzato nello stack la riga della chiamata (14). Non avendo il corpo principale dello script dati locali, ma solo dati globali non è memorizzato alcuno stato locale. Il controllo passa quindi alla prima riga di CountDown() avente una variabile locale $n con valore 50. Tale valore è mostrato a video, quindi alla riga 11 è invocata nuovamente la funzione CountDown($n-1) ossia con argomento pari a 49. Nello stack è quindi memorizzato 11 (la riga in cui avviene la chiamata) e lo stato locale ossia la variabile $n con valore 50. E' quindi trasferito il controllo alla prima riga di CountDown() (una nuova chiamata) avente una variabile locale con valore 49. Tale valore è mostrato a video, quindi alla riga 11 è invocata nuovamente la funzione CountDown($n-1). L'esecuzione andrà avanti così, mostrando a video i valori 50,49,48,47,.... mentre lo stack si riempie di chiamate. Si arriverà al punto in cui lo stack sarà pieno, ossia l'area dati a disposizione dello stack sarà esaurita, ottenendo un errore in esecuzione.
Arriviamo quindi a stabilire le due regole che dominano la ricorsione:
- Perché una funzione sia ricorsiva deve invocare almeno una volta se stessa
- Una funzione ricorsiva deve sempre prevedere una condizione che ponga fine alla ricorsione stessa.
Nel caso della nostra funzione CountDown() la ricorsione deve avere luogo fin tanto che $n>0. Completiamo quindi la funzione con il codice seguente:
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title></title>
</head>
<body>
<?php
function CountDown($n){
echo "$n<br>";
if($n>0)
CountDown($n-1);
}
CountDown(50);
?>
</body>
</html>
Aggiungendo una semplice condizione facciamo in modo che le chiamate ricorsive abbiano termine se $n>0. Raggiunto lo 0 la ricorsione termina e le varie chiamate che popolano lo stack sono ripristinate man mano che terminano le funzioni CountDown() invocate. Ciò fino a quando il controllo non ritorna al chiamante che ha dato origine alla ricorsione ossia il corpo principale dello script e la pila delle chiamate ricorsive è vuota.
E se volessimo ottenere un CountUp() da 0 a un certo numero n>0?
Molto semplicemente lasceremo eseguire subito tutte le ricorsioni fino a raggiungere lo 0, quindi inizieremo a stampare il risultato con 0. Si ripristina il chiamante dallo stack e appare 1, si ripristina la chiamante e appare 2 e man mano che si svuota lo stack, e le variabili locali dei chiamanti sono ripristinate otteniamo valori sempre maggiori fino al massimo utilizzato per dare il via alla ricorsione. In altre parole ci basta porre l'istruzione di output dopo la ricorsione e sfruttare la pila delle chiamate per ottenere l'ordine dei risultati dal più piccolo al più grande come mostrato nell'esempio seguente:
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title></title>
</head>
<body>
<?php
function CountUp($n){
if($n>0)
CountUp($n-1);
echo "$n<br>";
}
CountUp(50);
?>
</body>
</html>
L'esempio classico ossia il calcolo del fattoriale
Proviamo ora la ricorsione con l'esempio più classico che esista, ossia il calcolo del fattoriale. Per definizione n! è definito per tutti i numeri naturali come 0!=1 o n!=n*(n-1)! quando n diverso da 0.Come si può notare il fattoriale è definito in ragione di se stesso ed ha una condizione limite che conclude la ricorsione per n=0 che ritorna 1. possiamo quindi scrivere la nostra funzione fattoriale in cui bisogna verificare che l'argomento sia un numero naturale, e quindi porre la nostra condizione in cui se n è 0 ritorna 1 altrimenti ritorna al chiamante n*fattoriale(n-1). Otterremo il codice seguente:
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title></title>
</head>
<body>
<?php
function fattoriale($n){
if(!is_int($n) or $n<0)
exit('Errore! Il fattoriale è definito per i soli numeri naturali.');
if($n>0)
return $n*fattoriale ($n-1);
else
return 1;
}
echo fattoriale(5);
?>
</body>
</html>
Come si può notare il primo if verifica che $n contenga un numero intero positivo o 0. Soddisfatta tale condizione si ha la sezione ricorsiva simile al CountDown() precedente e che termina per n=0. La funzione in questo caso ritorna il proprio valore al chiamante che lo utilizza con il proprio argomento locale per il calcolo del fattoriale. Per vedere chiaramente ciò che avviene si osservi l'immagine seguente che mostra la pila dello stack e i vari valori ritornati dalle chiamate.
 |
| A destra, dal basso verso l'alto, le chiamate effettuate dalla ricorsione. Nella seconda colonna la variabile locale $n memorizzata nello stack ad ogni chiamata. Nella terza colonna il calcolo eseguito dal ramo if e in quarta colonna il valore conseguentemente ritornato dalla chiamata. In quinta colonna quello che è stato calcolato |
Simulare la ricorsione per mezzo dell'iterazione
La chiamata ricorsiva non è altro che un doppio ciclo in cui il primo compie delle azioni pre-ricorsione e popola lo stack ed il secondo estrae dallo stack e compie delle azioni post-ricorsione.Le azioni pre-ricorsione sono quelle che precedono la chiamata ricorsiva nella funzione ricorsiva, mentre le azioni post-ricorsione sono quelle che sono eseguite dopo la chiamata ricorsiva nella funzione ricorsiva. Proviamo ad implementare la funzione fattoriale() simulando la ricorsione tramite l'iterazione.
Procediamo lentamente alla stesura del codice. Vogliamo definire una funzione fattoriale($n) che calcoli il fattoriale. Di certo anche questa come la precedente dovrà avere il controllo sul $n affinché sia un numero naturale, e dovrà definire una variabile $stack che simulerà lo stack dell'applicazione oltre ad una variabile $ret_var che simulerà il la return contenendo il valore da ritornare alla fine dell'esecuzione della funzione ricorsiva.
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title></title>
</head>
<body>
<?php
function fattoriale($n){
if(!is_int($n) or $n<0)
exit('Errore! Il fattoriale è definito per i soli numeri naturali.');
$stack = array(); // Lo stack che memorizza le chiamate ricorsive
$ret_var = null; // La variabile che contiene il valore ri ritorno di ogni chiamata
//...
return $ret_var;
}
echo fattoriale(6);
?>
</body>
</html>
Abbiamo poi detto che al suo interno trovano posto due cicli di cui uno destinato a popolare lo stack (chiamate ricorsive) e l'altro a svuotarlo (termine delle chiamate ricorsive e ripristino chiamata precedente).
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title></title>
</head>
<body>
<?php
function fattoriale($n){
if(!is_int($n) or $n<0)
exit('Errore! Il fattoriale è definito per i soli numeri naturali.');
$stack = array(); // Lo stack che memoricca le chiamate ricorsive
$ret_var = null; // La variabile che contiene il valore ri ritorno di ogni chiamata
//Ciclo pre-ricorsione che popola lo stack
while(true){
//...
}
// ciclo post-ricorsione
while (true){
//...
}
return $ret_var;
}
echo fattoriale(6);
?>
</body>
</html>Nel primo ciclo avviene l'avvio delle chiamate ricorsive e le operazioni pre-ricorsione. Avvio che deve avvenire fin tanto che $n>0. Se $n non è maggiore di 0 allora è restituito il valore 1 ossia $ret_val=1 e la ricorsione termina. Se invece è maggiore di 0 il calcolo prevede la ricorsione ossia l'archiviazione nello stack della variabile locale $n e l'avvio di una chiamata ricorsiva (iterazione successiva) con $n decrementato di 1. Altra operazione pre-ricorsione è il controllo affinché $n sia un numero naturale, ma dato che eseguita la verifica per il primo valore passato come argomento, lo stesso è verificato per tutte le chiamate ricorsive successive questo è stato posto prima del ciclo.
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title></title>
</head>
<body>
<?php
function fattoriale($n){
if(!is_int($n) or $n<0)
exit('Errore! Il fattoriale è definito per i soli numeri naturali.');
$stack = array(); // Lo stack che memoricca le chiamate ricorsive
$ret_var = null; // La variabile che contiene il valore ri ritorno di ogni chiamata
//Ciclo pre-ricorsione che popola lo stack
while(true){
if($n>0) //Condizione di fine ricorsione
array_push ($stack, $n--); // Salvo lo stato locale
// per la chiamata successiva decrementato $n
else{
$ret_var = 1; // valore di ritorno per il
break; // caso limite e fine ricorsione
}
}
// ciclo post-ricorsione
while (true){
//...
}
return $ret_var;
}
echo fattoriale(6);
?>
</body>
</html>Ora non ci resta che il codice per il ciclo post-ricorsione, ossia quando una chiamata termina e il controllo ritorna al chiamante. In questo caso il valore ritornato ($ret_var) è moltiplicato per la variabile locale $n e ritornato a sua volta (assegnato a $ret_var). Quando tutte le chiamate sono terminate ossia lo stack è vuoto abbiamo terminato il ciclo post-ricorsione.
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title></title>
</head>
<body>
<?php
function fattoriale($n){
if(!is_int($n) or $n<0)
exit('Errore! Il fattoriale è definito per i soli numeri naturali.');
$stack = array(); // Lo stack che memoricca le chiamate ricorsive
$ret_var = null; // La variabile che contiene il valore si ritorno di ogni chiamata
//Ciclo pre-ricorsione che popola lo stack
while(true){
if($n>0) //Condizione di fine ricorsione
array_push ($stack, $n--); // Salvo lo stato lo cale
// per la chiamata successiva
else{
$ret_var = 1; // valore di ritorno per il
break; // caso limite e fine ricorsione
}
}
// ciclo post-ricorsione
while (true){
if(!is_null($n = array_pop($stack)))// Rirpistino lo stato precedente
$ret_var = $n * $ret_var; // Calcolo il valore di ritorno
else
break; //Quando lo stack è vuoto la ricorsione è conclusa
}
return $ret_var;
}
echo fattoriale(6);
?>
</body>
</html>Questo è tutto. Ecco come una chiamata ricorsiva può essere scritta in modo iterativo, ossia utilizzando due cicli per simulare la ricorsione. Ma ciò significa anche che un qualunque metodo ricorsivo può sempre essere scritto in modo iterativo, ossia come ciò che all'inizio del post ritenevamo divino è in realtà qualcosa di molto umano. Certo quello visto non è il modo migliore di implementare la funzione fattoriale in modo iterativo, ma è un metodo sempre applicabile indipendentemente dalla funzione ricorsiva in oggetto.
Un esempio dal mondo reale
In matematica esistono molti esempi di calcolo che sfruttano la ricorsione. Ma la ricorsione si applica solo ai conti? Certo che no. Per finire prendiamo in considerazione un esempio dal mondo reale. In un forum in cui sono registrato come Grino mi è capitato d'imbattermi in un utente che poneva il seguente quesito (discussione originale): Come creare un menu a tendina partendo da dei record che contengono le categorie/sottocategorie memorizzate nel modo seguente di cui però non è nota la profondità a priori?
elettrodomestici
elettrodomestici>cucine>elettriche
elettrodomestici>cucine>gas
forni
forni>da incasso
forni>da incasso>a gas
forni>da incasso>elettrici
forni>esterni
forni>esterni>a gas
forni>esterni>elettrici
televisori
televisori>LED
televisori>LED>32 pollici
televisori>LED>40 pollici
televisori>plasma
televisori>plasma>32 pollici
televisori>plasma>40 pollici
La prima cosa che ho pensato di fare è organizzare il dato in una struttura migliore utilizzando gli array di PHP che di fatto sono delle mappe chiave-valore. I vari letterali "elettrodomestici", "da incasso", "32 pollici", ecc. devono essere chiavi, di modo che non possano essere duplicati a parità di livello. Ad ogni chiave appartiene un valore array per cui ad esempio dentro "forni" avremo un array i cui valori hanno chiavi "esterni" e "da incasso". Questi due elementi al loro interno hanno degli array le cui chiavi sono per "da incasso", "a gas" e "elettrici", mentre per "esterni" ci saranno ancora i due elementi con chiave "a gas" e "elettrici". Le foglie, come "a gas", di questa struttura saranno banalmente degli array vuoti. Più semplicemente, partendo dall'array di stringhe precedente, ottenuto da una interrogazione a un DB, voglio ottenere quello che segue:
Array(
[elettrodomestici] => Array(
[cucine] => Array(
[elettriche] => Array()
[gas] => Array()
)
)
[forni] => Array(
[da incasso] => Array(
[a gas] => Array()
[elettrici] => Array()
)
[esterni] => Array(
[a gas] => Array()
[elettrici] => Array()
)
)
[televisori] => Array(
[LED] => Array(
[32 pollici] => Array()
[40 pollici] => Array()
)
[plasma] => Array(
[32 pollici] => Array()
[40 pollici] => Array()
)
)
)Per ottenere questo risultato avremo bisogno di popolare un variabile $menu che alla fine contenga questa struttura. Per popolarla possiamo pensare ad una funzione ricorsiva addToMenu() che s'invochi fino a quando tutte le voci della stringa non sono inserite in struttura. Più precisamente, per ogni stringa si procede alla sua esplosione sul carattere > in elementi di un array. S'inverte l'ordine dell'array in modo da trattarlo come uno stack, tramite la funzione array_pop(), ed in modo da estrarre le voci dal livello 1 degli elementi della struttura verso i livelli più profondi. Per ogni voce estratta dallo stack delle voci si verifica l'esistenza e se non esiste nella struttura, la stessa è creata (utilizzandola come chiave) assegnandole un array vuoto. S'invoca quindi ricorsivamente la funzione addToMenu() passandole al posto della radice della struttura l'elemento appena verificato/creato perchè sia nuova radice cui appendere le voci successive ancora presenti nello stack delle voci.
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title></title>
</head>
<body>
<?php
//ipotetico recordset generato da una interrogazione al DB
$recordset = array(
"elettrodomestici",
"elettrodomestici>cucine>elettriche",
"elettrodomestici>cucine>gas",
"forni",
"forni>da incasso",
"forni>da incasso>a gas",
"forni>da incasso>elettrici",
"forni>esterni",
"forni>esterni>a gas",
"forni>esterni>elettrici",
"televisori",
"televisori>LED",
"televisori>LED>32 pollici",
"televisori>LED>40 pollici",
"televisori>plasma",
"televisori>plasma>32 pollici",
"televisori>plasma>40 pollici"
);
function addToMenu(&$menu, $voci) {
if (!is_null($voce = array_pop($voci))) { //Ci sono anco voci nello stack delle voci?
if (!isset($menu[$voce])) // Se la voce estratta non esiste,
$menu[$voce] = array(); //la creo assegnandole un array vuoto
addToMenu($menu[$voce], $voci); //Continuo ad assegnare le voci all struttura partendo dalla voce attuale
}
}
$menu = array(); //La varibile contenente la nostra struttura dati
foreach ($recordset as $value) {
$voci = array_reverse(explode(">", $value)); //Creo lo stack delle voci di un record
addToMenu($menu, $voci); //Chiedo alla funzione di aggiungere le voci al mio menu
}
?>
</body>
</html>Ora che abbiamo strutturato i dati, non resta che utilizzare tale struttura per produrre un menu a tendina. Ossia stampare i nostri tag di <select> e chiedere ad una funzione showMenu($menu) di visualizzare il menu (le varie <option>). Questa funzione dovrà percorrere tutta la struttura, mostrando la voce attuale e sfruttando la ricorsione per le sottostrutture di cui la profondità non è nota. In altri termini, partita la ricorsione con argomento $menu, occorre visualizzare ogni chiave dell'array e per ogni struttura pendente sotto la chiave visualizzata invocare nuovamente showMenu() dandole come argomento la struttura che pende al disotto della chiave appena visualizzata.
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title></title>
</head>
<body>
<?php
$recordset = array(
"elettrodomestici",
"elettrodomestici>cucine>elettriche",
"elettrodomestici>cucine>gas",
"forni",
"forni>da incasso",
"forni>da incasso>a gas",
"forni>da incasso>elettrici",
"forni>esterni",
"forni>esterni>a gas",
"forni>esterni>elettrici",
"televisori",
"televisori>LED",
"televisori>LED>32 pollici",
"televisori>LED>40 pollici",
"televisori>plasma",
"televisori>plasma>32 pollici",
"televisori>plasma>40 pollici"
);
function addToMenu(&$menu, $voci) {
if (!is_null($voce = array_pop($voci))) {
if (!isset($menu[$voce]))
$menu[$voce] = array();
addToMenu($menu[$voce], $voci);
}
}
function showMenu($menu) {
static $indent = 0;
foreach ($menu as $key => $value) {//Creo la option di ogni voce della struttura
echo '<option>'.str_repeat(' ',$indent)."$key</option>";//in argomento
if (is_array($menu[$key])){// Se la voce ha una sottostruttura effettuo una $indent++; //ricorsione e chiedo a showmenu di lavorare sulla sottostruttura
showMenu($menu[$key]);
$indent--;
}
}
}
$menu = array();
foreach ($recordset as $value) {//qui sostituisci con mysql_fetch_array
$voci = array_reverse(explode(">", $value));
addToMenu($menu, $voci);
}
echo "<select>";
showMenu($menu);
echo "</select>";
?>
</body>
</html> |
| Il risultato dello script |
Sempre dallo stesso forum, un'altro esempio cui ho risposto fornendo una funzione ricorsiva.
Conclusione
La ricorsione non ha nulla di divino, ma è solo un altro mattoncino della programmazione. Come tale lo si conosce per poterlo sfruttare al meglio. Un problema definito ricorsivamente riduce quasi sempre la lunghezza del codice dando, a detta degli esteti degli algoritmi, un aspetto più elegante al codice. D'altra parte la lettura del codice è un po' più complessa poichè esistono diversi fattori da tenere in considerazione. Di norma se si è compreso il problema la ricorsione riesce a fornire una soluzione più semplice da implementare rispetto all'iterazione grazie ad involontari meccanismi che s'innescano quali lo stack delle chiamate che produce un'archiviazione di dati parziali, lo sfruttamento della return al posto della variabile accumulatore, l'eliminazione di cicli sostituiti da chiamate alla funzione stessa.
