Giuseppe Dell'Abate's Blog

Translate in English with Google Translate
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:

1. 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.
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.
3. 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.
4. 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:
5. 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;
6. 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;
7. 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

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.

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]);
  }
}

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 backslash \\ indicando C:\\progetti. Il primo backslash serve per definire caratteri speciali, mentre il secondo backslash 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 slash invece del doppio backslash: 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 o Pila
• Heap

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:

1. 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.
2. 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.
3. 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.

L’esito del test mostra che il compilatore JIT migliora di molto le prestazioni anche di un fattore 12 maggiori dell’interprete.

In un successivo articolo, sfruttando la memoizzazione, sarà possibile ottimizzare in larga misura i tempi di esecuzione delle procedure ricorsive riducendo al minimo l’utilizzo della memoria ed ottimizzando i tempi di CPU.

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.