Ricorsione In Java

– Indice Tutorial –

La ricorsione è una tecnica di programmazione che permette di creare dei metodi che, durante la loro esecuzione, chiamano, direttamente o indirettamente, se stessi, fino a quando una condizione viene rispettata, terminando questo ciclo di auto – chiamate.

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, ma di dimensione più piccola, fino a raggiungere una dimensione minima che da un risultato finito.

Il classico esempio di applicazione della ricorsione è 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 (che si indica con 3!) 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 à qua le auto-chiamate si bloccano, essendo 1 il fattoriale di 0. A questo punto si ritorna a ritroso nelle chiamate precedenti, quindi a 1! e poi 2! e infine a 3!

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

Notare che la condizione di termine delle 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, sostituendo 3! con fattoriale(3), stessa cosa per gli altri numeri si ha:

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)

In java si ha:

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

Video Lezione Sulla Ricorsione