La ricorsione in Java

Nel linguaggio Java ogni metodo può essere ricorsivo. Un metodo ricorsivo altro non è che un metodo che richiama se stesso. Affinché la ricorsione sia corretta e non generi cicli infiniti occorre:

• la presenza di una condizione di terminazione, in parole povere, almeno una volta il metodo non dovrà richiamare se stesso;
• ad ogni chiamata ricorsiva ci si avvicini alla condizione di terminazione, cioè venga effettuato un passo di ricorsione;

La ricorsione e l’iterazione sono teoricamente equivalenti, la differenza se vogliamo sta nel fatto che il più delle volte l’iterazione privilegia l’efficienza dell’esecuzione, mentre la ricorsione la semplicità di codifica.

Cerchiamo di chiarire la differenza con un esempio:

Supponiamo di voler calcolare il massimo comune divisore tra due numeri positivi x ed y, rispettivamente di valore 10 e 6. Analizziamo la soluzione iterativa:

[sourcecode language=’java’]
int mcd_iterativo(int x, int y){
while(true){
if(x == y || y==0){ //comprende anche il caso 0
return x;
}else if(x==0){
return y;
}else if(x > y){
x -= y;
}else{
y -= x;
}
}
}
[/sourcecode]
Si è utilizzato un cliclo while per iterare sino a che non si arriva ad una soluzione (return riga 04), utilizzando la ricorsione invece:

[sourcecode language=’java’]
int mcd_ricorsivo(int x, int y){
if (y==0)
return x;
else
return mcd_ricorsivo(y , x%y);
}
[/sourcecode]

Le chiamate ricorsive (return mcd_ricorsivo(y , x%y) riga 05) sono 4 e precisamente:

mcd (10,6)
mcd (6,4)
mcd (4,2)
mcd (2,0)

L’ultima chiamata ricorsiva determinerà il risultato 2.
Il codice è sicuramente più compatto.