|
La ricorsione (recursion) è una tecnica di
programmazione molto potente, che sfrutta l'idea di suddividere un
problema da risolvere in sottoproblemi simili a quello originale, ma
più semplici.
Esempio: Supponiamo di voler calcolare l'area di una
forma triangolare di dimensione n come quella riportata sotto,
nell'ipotesi che ciascun quadrato [] abbia area unitaria. Il valore
dell'area corrispondente viene a volte chiamato numero triangolare
n-esimo.
Ad esempio, per n=4 il triangolo è fatto come segue:
[]
[][]
[][][]
[][][][]
Osservando questo schema possiamo affermare che il quarto numero triangolare è 10.
Supponiamo di voler scrivere un metodo che dato n, calcola il numero triangolare
n-esimo.
public static int numeroTriangolare(int n) {
int result;
.....
return result;
}
|
Ragioniamo per approssimazioni successive.
Se l'ampiezza del triangolo è 1, il triangolo consiste di un
unico quadrato [] e la sua
area è uguale a 1.
public static int numeroTriangolare(int n) {
int result;
if (n == 1)
result = 1; // caso base
......
return result;
}
|
Per trattare il caso più generale, consideriamo questa figura:
[]
[][]
[][][]
[][][][]
Supponiamo adesso di conoscere l'area del triangolo più piccolo, formato dalle prime tre righe: il terzo numero triangolare. In questo caso possiamo calcolare facilmente l'area del triangolo grande: il quarto numero triangolare:
risultato = n + numero_triangolare_di_n-1;
Come possiamo calcolare il valore di numero_triangolare_di_n-1?
Facciamolo calcolare a( una diversa istanza de)lla funzione numeroTriangolare() che stiamo definendo.
risultato = n + numeroTriangolare(n-1);
public static int numeroTriangolare(int n) {
int result;
if (n == 1)
result = 1; // caso base
else
result = n + numeroTriangolare(n - 1); // ricorsione
return result;
}
|
|
La soluzione appena trovata presenta un aspetto interessante:
per risolvere il problema di calcolare l'area del triangolo di ampiezza assegnata abbiamo usato il fatto di poter risolvere lo stesso problema per un'ampiezza minore.
Questa viene chiamata soluzione ricorsiva.
Nel nostro caso, per risolvere il problema di calcolare l'n-esimo numero triangolare (l'area del triangolo di ampiezza n) abbiamo usato il seguente metodo:
-
siamo partiti dal saper calcolare l'area del triangolo di ampiezza 1,
-
abbiamo calcolato l'area del triangolo di ampiezza n supponendo di saper calcolare l'area del triangolo di ampiezza n-1.
Un algoritmo
ricorsivo per la risoluzione di un dato problema deve
essere definito nel modo seguente:
- prima si definisce come risolvere dei problemi analoghi a quello
di partenza, ma che hanno "dimensione piccola" e possono
essere risolti in maniera estremamente semplice (detti casi base);
- poi si definisce come ottenere la soluzione del problema di
partenza combinando la soluzione di uno o più problemi analoghi,
ma di "dimensione inferiore".
|
|
Un metodo si dice
ricorsivo quando all'interno della propria definizione
compare una chiamata direttamente al metodo stesso.
Questa forma di ricorsione si chiama ricorsione
diretta.
Un esempio di ricorsione diretta
è il metodo che abbiamo realizzato precedentemente:
public static int numeroTriangolare(int n) {
int result;
if (n == 1)
result = 1; // caso base
else
result = n + numeroTriangolare(n - 1); // ricorsione
return result;
}
|
Condizioni come
(n == 1) si chiamano
clausole di chiusura o casi base perché garantiscono che la ricorsione
termini.
Esistono due requisiti che sono basilari per essere sicuri che la ricorsione funzioni:
-
ogni invocazione ricorsiva deve semplificare in qualche modo l'elaborazione,
- devono esistere casi speciali che gestiscano in modo diretto le elaborazioni più semplici.
Il medodo numeroTriangolare chiama se stesso con valori di ampiezza sempre più piccoli; l'ampiezza prima o poi diventa uguale a 1 che è il caso speciale che vale 1.
Occorre però fare molta attenzione: cosa succede se chiedete l'area del triangolo di ampiezza -1?
Per evitare ciò il metodo numeroTriangolare dovrebbe restituire 0 se l'ampezza è minore di 0.
In questo modo il metodo numeroTriangolare riuscirebbe sempre a concludere la propria elaborazione.
public class MyRecursiveMethods {
// altri metodi
public static int numeroTriangolare(int n) {
int result;
if (n < 0)
result = 0; // situazione anomala
else if (n == 1)
result = 1; // caso base
else
result = n + numeroTriangolare(n - 1); // ricorsione
return result;
}
// altri metodi
}
|
|
|
La ricorsione non era veramente necessaria per calcolare l' n-esimo numero triangolare che poteva essere calcolato semplicemente usando la nota equivalenza per la somma dei primi n numeri positivi:
1 + 2 + 3 +...+ n = n * (n+1)/2
Vediamo adesso l'esempio di una formula simile ma non calcolabile direttamente: la funzione fattoriale.
n! = n * (n - 1)* ... * 3 * 2 * 1
Per convenzione 0! =
1. Inoltre, il fattoriale non è definito per i
numeri negativi.
Nella lezione sui cicli abbiamo visto come
calcolare il fattoriale in modo iterativo. Come possiamo invece scrivere un
metodo ricorsivo che calcoli la funzione fattoriale? Osserviamo
che:
n! = n * (n-1) * ... * 2 * 1 =
= n * (n-1)!
Quindi la definizione induttiva del fattoriale è:
0! = 1 (caso base)
n! = n * (n-1)! (se n > 0).
Seguendo tale descrizione possiamo agiungere il metodo ricorsivo fattoriale alla classe dei nostri metodi.
public class MyRecursiveMethods {
// altri metodi
public static int factorial(int n) {
int result;
if (n < 0)
result = -1; // situazione anomala
else if (n == 0)
result = 1; // caso base
else
result = n * factorial(n - 1); // ricorsione
return result;
}
// altri metodi
}
|
  |
Come funziona la Ricorsione? (1)
|
 
|
|
Supponiamo di eseguire il metodo
public static void main (String [] args) {
...
int i = MyRecursiveMethods.factorial(3);
...
}
|
Per l'invocazione di
factorial(3), il record di attivazione è
aggiunto in cima alla pila (con una operazione di push), e i
record relativi alle successive invocazioni di
factorial vengono "impilati" su di
esso (mediante operazioni di push successive).
|
|
Come funziona la Ricorsione? (2)
|
|
|
Arrivati al caso base i record iniziano
ad essere "scaricati" dalla pila restituendo mano a mano i valori
ottenuti e passando il controllo al corrispondente indirizzo di ritorno.
Quando una chiamata di factorial
termina, il corrispondente record di attivazione è eliminato
(operazione di pop).
Alla fine, il flusso continua dall'indirizzo di
ritorno nel main da dove il metodo è stato chiamato per la prima volta.
|
| Si parla di ricorsione indiretta
quando nella definizione di un metodo compare la
chiamata ad un altro metodo il quale direttamente o indirettamente
chiama il metodo iniziale.
Un esempio di ricorsione indiretta:
public class MyRecursiveMethods {
... // altri metodi
// notare che si restituisce direttamente il risultato,
// evitando l'uso della variabile locale result
public static int ping(int n) {
if (n < 1)
return 1;
else
return pong(n - 1); // chiamata di pong
}
public static int pong(int n) {
if (n < 0)
return 0;
else
return ping(n/2); // chiamata di ping
}
... // altri metodi
}
|
Notare che, nell'esempio sopra, i metodi sono cooperanti nel senso che
si invocano ripetutamente a
vicenda (indirettamente), dando luogo ad un caso particolare di
ricorsione indiretta, detto ricorsione mutua.
|
| Un metodo implementa
una ricorsione multipla quando
all'interno della propria definizione compare la
chiamata direttamente al metodo stesso almeno
due volte.
Un classico esempio di ricorsione multipla è
l'implementazione dei numeri di Fibonacci, la cui definizione è riportata sotto:
fib(0) = 0
fib(1) = 1
fib(n) = fib(n - 1) + fib(n - 2) (se n > 1) |
Notare che, come per il fattoriale, la funzione è definita solo su interi non negativi.
In Java il metodo per l'implementazione dei numeri di Fibonacci
può essere definito come:
public class MyRecursiveMethods {
... // altri metodi
public static int fib(int n) {
if (n < 0)
return -1; // anomalie
else if ( n==0 || n==1 )
return n; // casi base
else
return fib(n-1) + fib(n-2); // ricorsione
}
... // altri metodi
}
|
|
|
Problemi con la Ricorsione
|
|
|
La ricorsione è una tecnica molto
potente per decomporre problemi complessi, ma quando si scrivono
programmi ricorsivi si incontrano tre problemi comuni:
- spazio sprecato: si scrivono metodi che contengono
variabili locali non necessarie, oppure non usate, e così la
memoria del sistema non è utilizzata in modo
efficiente (lo spazio sprecato si moltiplica per il numero di invocazioni ricorsive effettuate!).
- ricorsione infinita: è un grave errore di programmazione che tipicamente si verifica
perché manca la clausola di chiusura per terminare (errata gestione di anomalie e casi base) o
perché i valori del parametro non si semplificano (errata gestione delle chiamate ricorsive).
- complessità alta: per certi problemi le
soluzioni ricorsive hanno intrinsecamente complessità non
lineare.
Gli ultimi due problemi possono risultare particolarmente gravosi e quindi li esaminiamo più in dettaglio.
|
|
In una ricorsione infinita vengono attivate infinite istanze di un metodo. Come abbiamo già
detto, ciò si verifica perché i valori del parametro non
si semplificano, o perché manca la clausola di chiusura per
terminare.
Per esempio, vediamo cosa succede nell'implementazione del fattoriale quando omettiamo la gestione dei casi base:
public class MyRecursiveMethods {
... // altri metodi
public static int badFactorial(int n) {
return (n * badFactorial(n-1));
}
... // altri metodi
}
|
Dopo un certo numero di chiamate la memoria disponibile
per questo scopo si esaurisce e il programma termina automaticamente
segnalando un errore di trabocco della
pila (stack overflow error).
|
La tecnica della ricorsione non è sempre il modo migliore di
risolvere problemi. Un esempio di questa situazione è
evidenziato dall'albero delle chiamate per il metodo ricorsivo fib che abbiamo definito per il calcolo dei numeri di Fibonacci:
La complessità del
metodo fib(n)
è esponenziale perché la ricorsione è
multipla. Da un'analisi dell'algoritmo, i casi base (fib(0) o fib(1)) sono
calcolati complessivamente fib(n+1)
volte durante la computazione di fib(n).
- Ad esempio, per calcolare fib(29) i
metodi fib(0)
e fib(1)
sono chiamati fib(30) = 832040 volte.
Una banale implementazione con un ciclo che
calcola una ed una sola volta tutti i valori dei numeri di
Fibonacci da 0 a
n ha invece
una complessità lineare (ovviamente).
Per ovviare alla alta complessità dei
metodi ricorsivi possiamo sempre transformare i loro algoritmi in algoritmi
iterativi. Per esempio possiamo definire una versione iterativa
iterativeFactorial del metodo factorial: tale versione è tanto
leggibile quanto la versione ricorsiva.
In modo analogo si può scrivere una versione iterativa
iterativeFib del metodo
per calcolare i numeri di Fibonacci:
tale definizione ha
complessità lineare ma è meno leggibile.
public class MyIterativeMethods {
public static int iterativeFib(int n) {
int fibN = -1; // gestione casi anomali
if ( n==0 || n==1 )
fibN = n;
else {
// ad ogni iterazione bisogna ricordare gli ultimi
// due valori calcolati nelle iterazioni precedenti
int fibNminus2 = 0; // penultimo valore
int fibNminus1 = 1; // ultimo valore
for (int i = 2; i <= n; i++) {
fibN = fibNminus1 + fibNminus2;
fibNminus2 = fibNminus1;
fibNminus1 = fibN;
}
}
return fibN;
}
}
|
Per avere un'idea della differenza di prestazioni tra la
versione iterativa e quella ricorsiva proviamo a confrontare i tempi
di esecuzione per alcuni valori (es. 10,
20, 30, 40 e
45): FibonacciTest
.
|
| |
