La Ricorsione in Java

– Indice Tutorial –

La ricorsione è una tecnica di programmazione che permette di creare dei metodi ricorsivi, ossia dei metodi che, durante la loro esecuzione, chiamano, direttamente o indirettamente, se stessi.

Quando un metodo invoca sè stesso, la JVM esegue le seguenti azioni:

1. sospende l’esecuzione del metodo invocante
2. esegue il metodo invocato fino alla sua conclusione
3. riprende l’esecuzione del metodo invocante dal punto in cui era stata sospeso.

Per poter applicare questa tecnica, si deve decomporre un problema in problemi dello stesso tipo (cioè della stessa natura) ma di dimensione più piccola.

Ad esempio, supponiamo di voler creare un metodo ricorsivo per il calcolo del fattoriale di un numero n:

n!= n*(n-1)*(n-2)*…(n-(n-1))

se n è uguale a 3, il suo fattoriale sarà:

3!=3*(3-1)*(3-2)
3!=3*2*1
3!=6

Scritto in altro modo :

3!=3*2!
2!=2*1!
1!=1*0!
0!=1
1!=1*1=1
2!=2*1=2
3!=3*2=6

Notare che il fattoriale termine le sue chiamate quando si arriva al fattoriale di zero che è uno. Riscrivendo in italiano:

1. Per ottenere 3! occorre ricavare 2! (poiché 3!=3*2!)
2. Per ottenere 2! occorre ricavare 1! (poiché 2!=2*1!)
3. Per ottenere 1! occorre avere 0! (poiché 1!=1*0!)
4. 0!=1 possiamo risalire a ritroso e completare le esecuzione precendenti effettuando le sostituzioni dovute
5. Si ha che 1!=1*0!=1*1=1 (poiché 0!=1)
6. Si ha che 2!=2*1!=2*1=2 (poiché 1!=1)
7. Avremo infine che 3!=3*2!=3*2=6 (poiché 2!=2)

E ancora:

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

generalizzando in pseudocodice:

ricorsione(n)
	se n è uguale a 0 ritorna 1
	altrimenti
		richiama ricorsione(n-1)

Che in java diventa:

	int ricorsione(int x) {
		int fattoriale;
		if (x == 0)
			fattoriale = 1;
		else
			fattoriale = x * ricorsione(x - 1);
		return fattoriale;
	}

Notare l’importanza di 0! = 1, senza quella condizione il programma non si sarebbe mai fermato.