Introduzione
La ricorsione è una tecnica di programmazione
per eseguire operazioni che direttamente o indirettamente
richiamano se stessi.
Nella ricorsione viene invocato un metodo mentre questo
è in esecuzione. Il metodo che ne faccia uso
si chiama metodo ricorsivo. La ricorsione è uno
strumento molto potente per realizzare alcuni algoritmi,
ma è anche fonte di molti errori di difficile
diagnosi. La ricorsione è connessa al principio
di induzione matematica pertanto un concetto è
definito in termini induttivi se è definito in
termini di se stesso. La particolarità della
ricorsione è nel fatto che il metodo richiama
se stesso e questo comporta la sospensione del metodo
chiamante in attesa del risultato del metodo chiamato.
Viene impiegata quando una prima operazione per essere
completata deve eseguire una seconda operazione, questa
seconda operazione a sua volta per essere completata
deve eseguire una terza operazione, e cosi via. Quando
un'operazione per completarsi non richiederà
l'esecuzione di un'altra operazione, allora sarà
possibile completare tutte le operazioni che erano rimaste
in sospeso.
Si potrebbe pensare che non è possibile invocare
un metodo mentre si esegue il metodo stesso!
Invece questo è lecito in Java, così come
è lecito in quasi tutti i linguaggi di programmazione.
In Java la Virtual Machine alloca un diverso contesto
ogni volta che viene richiamato lo stesso metodo attraverso
la ricorsione. Questo comporta che le variabili sono
considerate localmente a scapito della richiesta di
memoria al sistema. Pertanto maggiore sarà l'annidamento
e maggiore sarà la memoria usata.
La ricorsione
Quando un metodo ricorsivo invoca se stesso, la macchina
virtuale Java esegue le stesse azioni che vengono eseguite
quando viene invocato un metodo qualsiasi:
1) sospende l'esecuzione del metodo invocante
2) esegue il metodo invocato fino alla sua terminazione
3) riprende l'esecuzione del metodo invocante dal punto
in cui era stata sospeso.
L'utilizzo
della tecnica della ricorsione viene utilizzata in tutti
quei casi in cui non è conveniente o non è
possibile utilizzare i cicli iterativi.
La ricorsione può essere di diversi tipi: ricorsione
in coda e ricorsione multipla. La ricorsione in coda
si presenta quando un metodo invoca se stesso una sola
volta mentre la ricorsione multipla avviene quando un
metodo invoca se stesso più volte. Prendiamo
come esempio del primo caso il numero fattoriale, mentre
per il secondo caso consideriamo il numero di Fibonacci.
Ricorsione in coda
La ricorsione in coda (tail recursion) si presenta quando
il metodo ricorsivo esegue una sola invocazione ricorsiva
e tale invocazione è l'ultima azione del metodo.
Viene utilizzata nei casi in cui la soluzione del problema
è esplicitamente ricorsiva.
Tale ricorsione può essere agevolmente eliminata,
trasformando il metodo ricorsivo in un metodo che usa
un ciclo. La ricorsione in coda si presenta meno efficiente
del ciclo in quanto viene utilizzata molta più
memoria per gestire le invocazione sospese nello stack
ma rispetto al ciclo presenta il codice molto più
leggibile.
Immaginiamo
che si voglia determinare un numero fattoriale partendo
dalla funzione fattoriale:
quindi:
n!=
n*(n-1)*(n-2)*...(n-(n-1))
pertanto
se vogliamo conoscere il fattoriale del numero 3, abbiamo:
3!=3*(3-1)*(3-2)
3!=3*2*1
3!=6
Volendo
utilizzare la ricorsione per la determinazione del numero
fattoriale, l'equazione:
n!= n*(n-1)*(n-2)*...(n-(n-1))
può essere anche scritta così:
n!= n*((n-1)!)
quindi
per ottenere il numero fattoriale, abbiamo:
3!=3*2!
2!=2*1!
1!=1*0!
0!=1
1!=1*1=1
2!=2*1=2
3!=3*2=6
Questo
spiega che:
1. Per ottenere 3! occorre prima di tutto ricavare 2!
(poiché 3!=3*2!)
2. A sua volta per ottenere 2! bisogna ottenere 1! (poiché
2!=2*1!)
3. Per ottenere 1! occorre avere 0! (poiché 1!=1*0!)
4. Assumendo che 0!=1 possiamo completare l'esecuzione
facendo le sostituzioni dovute
5. Abbiamo adesso che 1!=1*0!=1*1=1 (poiché 0!=1)
6. Quindi possiamo determinare 2!=2*1!=2*1=2 (poiché
1!=1)
7. Possiamo adesso risalire ancora per determinare 3!=3*2!=3*2=6
(poiché 2!=2)
Facendo
le dovute sostituzioni, abbiamo:
3!=3*2!
poiché 2!=2*1! sostituiamo...
3!=3*(2*1!) poiché 1!=1*0! sostituiamo...
3!=3*(2*(1*0!)) assumiamo che 0!=1
3!=3*(2*(1*1))
3!=3*(2*(1))
3!=3*2*1
3!=6
Da
questo esempio possiamo notare che lo svolgimento dell'operazione
può essere suddivisa in 2 blocchi di operazioni:
- nel
primo blocco vengono sospese le operazioni che non
possono essere eseguite fino a quando non si raggiunge
una condizione (in questo caso 0!=1).
- nel
secondo blocco vengono effettuate tutte le sostituzioni
partendo dall'ultima operazione sospesa (criterio
LIFO - Last In First Out).
Numero fattoriale in Java
Utilizziamo adesso la programmazione in Java per implementare
un metodo ricorsivo per ottenere un numero fattoriale,
creando un metodo che ci consenta di calcolare un fattoriale.
In questo esempio se passiamo come parametro un numero
di tipo intero al metodo ricorsione() otteniamo il suo
numero fattoriale.
int
ricorsione(int x) {
int fattoriale;
if (x==0)
fattoriale = 1;
else
fattoriale = x * ricorsione(x-1);
return fattoriale;
}
Esaminiamo
insieme cosa avviene se passiamo come parametro il numero
3:
- viene
verificata la prima condizione: if (x==0)
ma poiché x=3 viene eseguita la seconda condizione:
fattoriale = x * ricorsione(x-1);
Questa comporta che per determinare 3! occorre conoscere
2! pertanto verrà richiamato nuovamente il
metodo ricorsione() e verrà passato come parametro
il numero 2.
- viene
nuovamente verificata la prima condizione: if (x==0)
ma poiché x=2 viene eseguita la seconda condizione:
fattoriale = x * ricorsione(x-1);
Questa comporta che per determinare 2! occorre conoscere
1! pertanto verrà richiamato nuovamente il
metodo ricorsione() e verrà passato come parametro
il numero 1.
- viene
ancora verificata la prima condizione: if (x==0)
ma poiché x=1 viene eseguita la seconda condizione:
fattoriale = x * ricorsione(x-1);
Questa comporta che per determinare 1! occorre conoscere
0! pertanto verrà richiamato nuovamente il
metodo ricorsione() e verrà passato come parametro
il numero 0.
- viene
ancora verificata la prima condizione: if (x==0)
ma adesso x=0 pertanto verrà eseguita l'assegnazione
fattoriale = 1
A questo punto ci troviamo alla fine del primo blocco
e risaliamo lo stack delle chiamate dei metodi per
completare l'esecuzione dei metodi che sono rimasti
in sospeso.
Infatti l'ultimo metodo ritornerà al metodo
chiamante il valore della variabile fattoriale = 1:
- Risalendo
lo stack delle chiamate dei metodi abbiamo che:
fattoriale = x * ricorsione(x-1); corrisponde a: fattoriale
= 1 * 1;
ed anche adesso verrà ritornato il valore della
variabile fattoriale = 1 al suo metodo chiamante;
- Risaliamo
ancora al metodo chiamante in cui l'assegnazione sospesa
può completarsi:
fattoriale = x * ricorsione(x-1); corrisponde a: fattoriale
= 2 * 1;
e verrà ritornato il valore fattoriale =2 al
metodo chiamante;
- Risaliamo
ancora al metodo chiamante in cui l'assegnazione sospesa
può completarsi:
fattoriale = x * ricorsione(x-1); corrisponde a: fattoriale
= 3 * 2;
A questo punto la ricorsione ha termine e possiamo
ritornare il valore della variabile fattoriale = 6;
I
passaggi possono essere ricapitolati in:
1-
ricorsione(3) invoca ricorsione(2)
2- ricorsione(2) invoca ricorsione(1)
3- ricorsione(1) invoca ricorsione(0)
4- ricorsione(0) restituisce 1
5- ricorsione(1) restituisce 1
6- ricorsione(2) restituisce 2
7- ricorsione(3) restituisce 6
Figura 1 - ricorsione nel caso del numero fattoriale
Come ho detto in precedenza, la ricorsione può
sempre essere sostituita con l'utilizzo di un ciclo.
In questo caso la sostituzione non si presenta particolarmente
complicata ed è possibile pertanto creare agevolmente
un metodo non ricorsivo che permetta il calcolo del
nostro numero fattoriale:
public
int ciclo(int x) {
int fattoriale = 1;
while (x > 0) {
fattoriale = fattoriale * x;
x--;
}
return fattoriale;
}
L'utilizzo
del metodo ciclico invece del metodo ricorsivo comporta
una minore allocazione di memoria, pertanto ottimizza
le prestazioni. Ma vi sono alcuni casi in cui la realizzazione
di un metodo non ricorsivo risulta molto più
complicato.
Ricorsione multipla
Nell'esempio precedente del numero fattoriale abbiamo
esaminato il caso della ricorsione in coda che rappresenta
la situazione più semplice di ricorsione, in
cui l'invocazione del metodo avviene una sola volta.
Ma adesso passiamo ad esaminare il caso della ricorsione
multipla che consiste nel caso in cui il metodo invoca
se stesso più volte durante la sua esecuzione.
La ricorsione multipla è più difficile
da eliminare attraverso la creazione di un metodo non
ricorsivo, ma è comunque sempre possibile. Questo
perché il processore esegue delle istruzioni
in sequenza e non può tenere delle istruzioni
in attesa. Difatti anche un metodo ricorsivo viene trasformato
in sequenziale dall'interprete attraverso il runtime-stack
durante la fase di esecuzione. L'invocazione ricorsiva
multipla comporta una maggiore allocazione di memoria
e se non viene utilizzata con attenzione può
portare a programmi molto inefficienti.
Un esempio di ricorsione multipla è il numero
di Fibonacci, che effettua una doppia invocazione.
La funzione di Fibonacci è:
Per il calcolo del numero di Fibonacci vengono considerati
due casi basi: n=0 e n=1. Il calcolo viene ottenuto
attraverso una doppia invocazione ricorsiva al metodo
stesso che genera un albero di chiamate.
Nello schema seguente viene rappresentata l'alberatura
del metodo con l'indicazione dei parametri passati.
In rosso è indicato il flusso che viene generato
a seguito della prima invocazione.
Figura 2 - ricorsione nel caso del metodo di Fibonacci
La realizzazione di tale ricorsione contiene una doppia
invocazione al metodo ricorsivo e ciò comporta
una maggiore allocazione di memoria rispetto al caso
precedente del numero fattoriale. Di seguito riporto
il metodo ricorsivo in Java:
public int fibonacci(int n) {
if (n < 2)
return n;
else
return fibonacci(n-2) + fibonacci(n-1);
}
Anche
in questo caso è possibile realizzare un metodo
non interattivo per poter calcolare il numero di Fibonacci
public int fib(int n) {
int fib1 = 1, fib2 = 0, f = fib1 + fib2;
if (n < 2)
return n;
else {
for (int i = 2; i < n; ++i)
{
fib2 = fib1;
fib1 = f;
f = fib1 + fib2;
}
return f;
}
}
Ricorsione
sul File System
La tecnica della ricorsione permette di implementare
casi sempre più complessi, anche se il principio
di funzionamento resta decisamente lo stesso.
Una problematica che viene affrontata e risolta facilmente,
facendo ricorso all'uso della ricorsione, è rappresentata
dalla visualizzazione della struttura del File System.
Attraverso la ricorsione è, infatti, possibile
realizzare un metodo che ci permetta di stampare a video
tutte le cartelle ed i files presenti all'interno di
una cartella di partenza.
In
un File System distinguiamo le cartelle ed i file:
-
le cartelle sono dei contenitori di file
- i
file contengono delle informazioni.
Vogliamo
creare un metodo che ci consenta di stampare a video
la gerarchia della struttura del File System partendo
da una cartella iniziale.Per riuscire a visualizzare
l'intera struttura ad albero, bisogna entrare in tutte
le cartelle che si incontrano e visualizzare il loro
contenuto.
Dobbiamo gestire 2 condizioni:
- Se
incontriamo una cartella dobbiamo accedere al suo
interno per continuare la ricerca dei file
- Se
incontriamo un file dobbiamo stampare a video il suo
percorso
Ci
torna utile l'utilizzo della ricorsione perché
ci consente di poter visualizzare la struttura del File
System attraverso l'utilizzo di alcuni metodi.La classe
che ci ritorna particolarmente utile per il nostro esercizio
è rappresentata dalla classe File appartenente
al package java.io. Questa classe ci consente di poter
maneggiare il nostro File System alla ricerca dei files.
I metodi dalla classe File che c'interessano sono:
-
public boolean isFile() verifica se l'oggetto File
denotato da questo percorso è un file e ritorna
true in caso affermativo. Questo metodo ci è
utile per capire se si tratta di un file ed in questo
caso viene stampato a video il suo percorso.
- public
boolean isDirectory() verifica se l'oggetto File denotato
da questo percoso è una cartella e ritorna
true in caso affermativo. Questo metodo ci è
utile per capire se si tratta di una cartella e decidere
di accedere al suo interno per ricercare altri files.
- public
File [] listFile() ritorna un array di File che sono
costituiti da cartelle e files che si trovano al suo
interno. Questo metodo è molto importante per
poter implementare la ricorsione sul contenuto delle
cartelle che vengono di volta in volta processate.
Viene utilizzato quando occorre conoscere il contenuto
di una cartella.
- public
void toString() converte il percorso di un oggetto
File in una stringa. Questo metodo ci consente di
stampare a video il percorso dei files all'interno
del File System.
Esempio di ricorsione sul File System
Ipotizzando che la struttura della cartella C:\progetti
nel File System si presenti in questo modo:
C:\progetti
C:\progetti\progettoX
C:\progetti\progettoX\x1.doc
C:\progetti\progettoX\x2.doc
C:\progetti\progettoY
C:\progetti\progettoY\y1.doc
C:\progetti\progettoY\y2.doc
C:\progetti\progettoZ
C:\progetti\progettoZ\z1.doc
C:\progetti\progettoZ\z2.doc
Creiamo
adesso un metodo che ci consenta di poter visualizzare
il contenuto della cartella di partenza C:\progetti
void
cartelle(File files) {
//elenco dei file nella cartella files,
se files è una cartella
File [] elencoFile;
//verifica
se si tratta di un file
if
(files.isFile()) {
//visualizza
il percorso del file
System.out.println(files.toString());
}
//verifica
se si tratta di una cartella
else
if (files.isDirectory()) {
//visualizza
il percorso della cartella
System.out.println(files.toString());
//memorizza
un elenco di file e cartella che trova
elencoFile
= files.listFiles();
//cicla
all'interno di tutte le sottocartelle
for(int
i = 0; i < elencoFile.length; i++)
cartelle(elencoFile[i]);
}
}
Figura 3 - ricorsione nel File System
Passando come parametro la cartella C:\progetti verranno
determinati tutti i files e le cartelle in modo ricorsivo
che sono al suo interno. Per stabilire la cartella di
partenza bisogna creare un oggetto File. Possiamo utilizzare
il costruttore File(String pathname) passando come argomento
il path a partire dal quale iniziare la ricorsione sul
File System.
Esempio:
import
java.io.*;
public static void main(String[] args) {
FilesRicorsione fr = new FilesRicorsione();
File fl = new File("C:\\progetti");
fr.cartelle(fl);
}
Da
notare come in questo caso per richiamare la cartella
C:\progetti viene usato il doppio backslace \\ indicando
C:\\progetti. Il primo backslace serve per definire
caratteri speciali, mentre il secondo backslace serve
per indicare il carattere speciale che vogliamo visualizzare.
Per esempio \n serve per impostare il ritorno a capo,
\" serve per visualizzare il carattere doppio apice,
'\b' indica il backspace e cosi via. E' anche possibile
utilizzare lo slace invece del doppio backslace: C:/progetti.
Pila di attivazione
Il modello di esecuzione dei metodi è basato
sul meccanismo della pila di attivazione. Questo significa
che ogni volta che viene richiamato un metodo, viene
creato un nuovo record di attivazione associato al metodo
e inserito nella pila di attivazione. Il record di attivazione
contiene tutte le informazioni necessarie all'esecuzione
del metodo tra le quali le variabili locali.
Nell'esempio del numero fattoriale quando passiamo al
metodo il numero 3 verrà assegnato alla variabile
locale fattoriale il valore 3.
Quando verrà richiamato il metodo ricorsione()
verrà nuovamente dichiarata una variabile locale
fattoriale che non coincide con quella precedente. Nel
momento in cui viene richiamato ricorsivamente il metodo
ricorsione() ad ogni chiamata viene riconosciuto un
ambito distinto l'uno dall'altro.
Questo comporta che quando l'esecuzione del metodo è
sospesa, le variabili locali vengono associate al record
di attivazione del metodo e vengono inserite nella pila
di attivazione.
Approfondimento sull'utilizzo della memoria nella Java
Virtual Machine
L'utilizzo della tecnica della ricorsione comporta un
uso molto elevato della memoria in quanto l'annidamento
del metodo che è richiamato ricorsivamente può
comportare, se non gestito opportunamente, dei problemi
di stack overflow.
Per esempio se noi eseguiamo la classe sottostante,
si genererà una ricorsione infinita che terminerà
con un errore java.lang.StackOverflowError in quanto
il metodo viene richiamato all'infinito.
Questo perchè viene a crearsi un Overflow (trabocco)
nello stack di runtime.
class
Over {
//ricorsione
infinita
public
static void main(String[] args) {
main(args);
}
}
Per
comprendere la causa del problema che può generarsi
occorre capire come viene impiegata la memoria dalla
JVM.
La memoria in Java si può pensare sostanzialmente
divisa in due parti:
Stack
Nello Stack la memoria viene gestita dinamicamente ed
e' organizzata in segmenti che vengono allocati in corrispondenza
di ogni chiamata di metodo e eliminati in corrispondenza
del ritorno del metodo. Tali segmenti costituiscono
la memoria locale del metodo cui sono associati.
I dati memorizzati nello stack, cioè nella memoria
locale dei metodi, sono solo dati elementari(int, char,
float, etc.). Tra i valori elementari vi sono anche
i puntatori, che sono indirizzi, cioè in definitiva
numeri che identificano un registro nella memoria.
Heap
Nell'Heap vengono memorizzati gli oggetti e gli Array
che non sono mai memorizzati sullo stack ma che sono
accessibili mediante i puntatori che sono memorizzati
nello stack .
In Java non sono presenti esplicitamente i tipi puntatore,
come per esempio in C, ma lo sono implicitamente perché
sono puntatori tutti i riferimenti ad array ed oggetti.
Possiamo rappresentare i puntatori con delle frecce
che puntano a zone della heap.
La
memoria locale di un metodo contiene:
- I
registri per contenere i valori dei parametri del
metodo, se ci sono.
- I
registri per contenere i valori delle variabili che
sono state dichiarate nel metodo.
- Un
indirizzo di ritorno
Nell'allocazione
e distruzione delle memoria locali si seguono queste
regole fondamentali:
-
Quando un metodo inizia la sua esecuzione, una nuova
memoria locale viene allocata in cima allo stack.
Quindi la memoria locale del metodo in esecuzione
è sempre quella in cima allo stack.
- Quando
un metodo termina la sua esecuzione, la memoria locale
corrispondente alla sua attivazione, che si trova
in quel momento in cima allo stack, viene cancellata
dallo stack.
- Quando
termina l'esecuzione di un metodo, il metodo che torna
in esecuzione è sempre quello la cui memoria
locale affiora sullo stack, dopo la rimozione della
memoria locale del metodo che termina.
Quando
si esegue un programma (comando "java") s'inizia
l'esecuzione del metodo "main" partendo da
uno stack vuoto. La memoria locale del main sarà
quindi la prima ad essere inserita sullo stack, e sarà
di conseguenza l'ultima ad essere rimossa.
La
memoria locale di un metodo viene "costruita"
all'atto della sua attivazione e "distrutta"
quando la sua esecuzione viene terminata. Quindi le
memorie locali dei metodi vivono soltanto durante la
loro esecuzione. L'esecuzione di un metodo X può
contenere una chiamata ad un altro metodo Y. In questo
caso l'esecuzione di X viene sospesa per eseguire il
metodo Y ma non terminata, e la sua memoria locale resta
quindi allocata. Y può essere X stesso se X e'
ricorsivo, ma in corrispondenza della nuova attivazione
viene allocata una nuova memoria locale. Quindi nel
caso di metodi ricorsivi possono esistere più
memorie locali per lo stesso metodo, corrispondenti
a diverse attivazioni.
Le memorie locali dei metodi la cui attivazione e' aperta
sono allocate nella memoria in un preciso ordine, che
rappresentiamo mettendole una sopra l'altra, secondo
una struttura detta stack o pila.
Supponiamo
ora che venga terminata l'esecuzione del corpo di una
metodo X con l'esecuzione di una istruzione di return.
Si eseguono allora le seguenti operazioni.
- l'ultima
memoria locale sullo Stack (quello relativo all'attivazione
di M) viene rimosso dallo Stack.
- viene
trasferito il controllo al punto del programma da
cui era partita la chiamata che aveva attivato la
funzione.
Al
ritorno da una chiamata a un metodo diverso da "void"
viene restituito un valore. Se la chiamata di una funzione
occorreva all'interno di un'espressione tale valore
viene usato nella valutazione dell'espressione stessa.
La
strategia di gestione della memoria rende possibile
la definizione di metodi ricorsivi. In questo caso si
sfrutta intensamente il fatto che ogni attivazione di
un metodo si costruisce la propria memoria locale, e
quindi la memoria locale delle attivazioni sospese non
viene cancellata ma resta "congelata" nell'attesa
di essere riutilizzata più avanti.
Prestazioni
della JVM nelle diverse versioni del JDK
Ho effettuato un confronto di prestazioni nelle diverse
versioni del JDK attraverso l'impiego del numero di
Fibonacci per effettuare un test ricorsivo sulla macchina
virtuale.
L'interprete Java trasforma ogni bytecode (*.class)
in una sequenza di istruzioni in codice nativo per la
CPU utilizzata. Se quel codice deve essere rieseguito,
può essere utilizzato il codice binario elaborato
in precedenza, consentendo un notevole risparmio di
tempo nell'esecuzione(JIT).
L'obiettivo del test è di misurare il tempo impiegato
dall'interprete Java e dal compilatore JIT ed indicare
il rapporto tra le due esecuzioni.
I test sono stati eseguiti su un PC Pentium 1.33GHz,
Ram:128 MB, Sistema Operativo: Windows 2000 Professional.
Gli esiti del test sono da considerarsi indicativi.
Tabella 1 - confronto delle prestazioni per le varie
funzioni ricorsive in base a JVM differenti
L'esito del test mostra che il compilatore JIT migliora
di molto le prestazioni anche di un fattore 12 maggiori
dell'interprete.
Conclusioni
In questo articolo abbiamo esaminato il principio di
funzionamento della tecnica della ricorsione che può
permetterci di implementare delle funzionalità
in modo molto semplice. La ricorsione è molto
utile in tutti quei casi in cui i cicli iterativi richiedono
molto codice implementativo e rendono molto difficile
la manutenzione e la comprensione del codice. Le prestazioni
della JVM possono essere notevolmente migliorate attraverso
l'utilizzo della compilazione Just in Time.
Risorse
Il
sorgente di Fibonacci.java può essere scaricato
qui
Giuseppe
Dell'Abate è programmatore Java su piattaforma
Standard ed Enterprise Sun. Lavora come consulente Java
e si occupa di progetti per applicazioni distribuite.
Ha lavorato per delle società del settore IT
e TLC. Si occupa in particolar modo di programmazione
Object Oriented utilizzando il linguaggio Java. Ha tenuto
dei corsi di Java base ed avanzati su piattaforma Java
Enterprise.
|