Questo tutorial approfondito sulla ricorsione in Java spiega cos'è la ricorsione con esempi, tipi e concetti correlati e tratta anche della ricorsione rispetto all'iterazione:
Nelle esercitazioni precedenti di Java abbiamo visto l'approccio iterativo, in cui dichiariamo un ciclo e poi attraversiamo una struttura di dati in modo iterativo, prendendo un elemento alla volta.
Abbiamo anche visto il flusso condizionale, in cui manteniamo una variabile del ciclo e ripetiamo un pezzo di codice finché la variabile del ciclo non soddisfa la condizione. Per quanto riguarda le chiamate di funzione, abbiamo esplorato l'approccio iterativo anche per le chiamate di funzione.
In questa esercitazione discuteremo un approccio diverso alla programmazione, ovvero l'approccio ricorsivo.
Che cos'è la ricorsione in Java?
La ricorsione è un processo mediante il quale una funzione o un metodo richiama se stesso più volte. Questa funzione che viene richiamata più volte, direttamente o indirettamente, è chiamata "funzione ricorsiva".
Vedremo vari esempi per capire la ricorsione. Vediamo ora la sintassi della ricorsione.
Sintassi della ricorsione
Ogni metodo che implementa la ricorsione ha due parti fondamentali:
- Chiamata di metodo che può richiamare se stessa, cioè ricorsiva.
- Una precondizione che interrompe la ricorsione.
Si noti che una precondizione è necessaria per qualsiasi metodo ricorsivo, poiché se non si interrompe la ricorsione, questa continuerà a girare all'infinito, causando un overflow dello stack.
La sintassi generale della ricorsione è la seguente:
methodName (T parameters...) { if (precondition == true) //precondition o base condition { return result; } return methodName (T parameters...); //recursive call } Si noti che la precondizione è anche chiamata condizione di base, di cui si parlerà più diffusamente nella prossima sezione.
Capire la ricorsione in Java
In questa sezione cercheremo di capire il processo di ricorsione e di vedere come si svolge. Impareremo a conoscere la condizione di base, l'overflow dello stack, a vedere come un particolare problema può essere risolto con la ricorsione e altri dettagli del genere.
Condizione di base della ricorsione
Durante la stesura del programma ricorsivo, dobbiamo innanzitutto fornire la soluzione per il caso base, per poi esprimere il problema più grande in termini di problemi più piccoli.
Come un esempio, Possiamo prendere un classico problema di calcolo del fattoriale di un numero. Dato un numero n, dobbiamo trovare un fattoriale di n indicato con n!
Ora implementiamo il programma per calcolare il fattoriale n (n!) utilizzando la ricorsione.
public class Main{ static int fact(int n) { if (n == 1) // condizione di base return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } } Uscita
In questo programma, possiamo vedere che la condizione (n<=1) è la condizione di base e quando questa condizione viene raggiunta, la funzione restituisce 1. La parte else della funzione è la chiamata ricorsiva. Ma ogni volta che viene chiamato il metodo ricorsivo, n viene decrementato di 1.
Possiamo quindi concludere che alla fine il valore di n diventerà 1 o inferiore a 1 e a questo punto il metodo restituirà il valore 1. Questa condizione di base sarà raggiunta e la funzione si fermerà. Si noti che il valore di n può essere qualsiasi cosa, purché soddisfi la condizione di base.
Risoluzione di problemi con la ricorsione
L'idea di base dell'uso della ricorsione è quella di esprimere il problema più grande in termini di problemi più piccoli. Inoltre, è necessario aggiungere una o più condizioni di base per poter uscire dalla ricorsione.
Questo è già stato dimostrato nell'esempio del fattoriale precedente. In questo programma, abbiamo espresso il fattoriale n (n!) in termini di valori più piccoli e avevamo una condizione di base (n <=1) in modo che quando n raggiunge 1, possiamo abbandonare il metodo ricorsivo.
Errore di overflow dello stack nella ricorsione
Sappiamo che quando viene richiamato un metodo o una funzione, lo stato della funzione è memorizzato nello stack e viene recuperato quando la funzione ritorna. Lo stack viene utilizzato anche per il metodo ricorsivo.
Tuttavia, nel caso della ricorsione, potrebbe verificarsi un problema se non si definisce la condizione di base o se la condizione di base non viene in qualche modo raggiunta o eseguita. Se si verifica questa situazione, potrebbe verificarsi un overflow dello stack.
Consideriamo il seguente esempio di notazione fattoriale.
In questo caso abbiamo dato una condizione di base sbagliata, n==100.
public class Main { static int fact(int n) { if (n == 100) // condizione di base con conseguente overflow dello stack return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } } Quindi, quando n> 100 il metodo restituirà 1, ma la ricorsione non si fermerà. Il valore di n continuerà a diminuire all'infinito, poiché non c'è nessun'altra condizione che lo fermi. Questo andrà avanti finché lo stack non traboccherà.
Un altro caso si verifica quando il valore di n <100. Anche in questo caso il metodo non eseguirà mai la condizione di base e provocherà un overflow dello stack.
Esempi di ricorsione in Java
In questa sezione, implementeremo i seguenti esempi utilizzando la ricorsione.
#1) Serie di Fibonacci con la ricorsione
La serie di Fibonacci è data da,
1,1,2,3,5,8,13,21,34,55,…
La sequenza di cui sopra mostra che l'elemento corrente è la somma dei due elementi precedenti. Inoltre, il primo elemento della serie di Fibonacci è 1.
Quindi, in generale, se n è il numero corrente, allora è dato dalla somma di (n-1) e (n-2). Poiché l'elemento corrente è espresso in termini di elementi precedenti, possiamo esprimere questo problema utilizzando la ricorsione.
Il programma per implementare la serie di Fibonacci è riportato di seguito:
public class Main { //metodo per calcolare la serie di fibonacci static int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n-1) + fibonacci(n-2); } public static void main(String[] args) { int number = 10; //stampa dei primi 10 numeri della serie di fibonacci System.out.println ("Serie di Fibonacci: primi 10 numeri:"); for (int i = 1; i <= number; i++) { System.out.print(fibonacci(i) + " ");} } } Uscita
#2) Controllare se un numero è palindromo usando la ricorsione
Un palindromo è una sequenza che è uguale quando la si legge da sinistra a destra o da destra a sinistra.
Dato un numero 121, vediamo che quando lo leggiamo da sinistra a destra e da destra a sinistra è uguale. Quindi il numero 121 è palindromo.
Prendiamo un altro numero, 1242. Quando lo leggiamo da sinistra a destra è 1242 e quando lo leggiamo da destra a sinistra è 2421. Quindi non si tratta di un palindromo.
Implementiamo il programma palindromo invertendo le cifre dei numeri e confrontando ricorsivamente il numero dato con la sua rappresentazione inversa.
Il programma seguente implementa il programma per verificare il palindromo.
import java.io.*; import java.util.*; public class Main { // controlla se il numero contiene una sola cifra public static int oneDigit(int num) { if ((num>= 0) && (num <10)) return 1; else return 0; } //funzione di utilità di palindromo public static int isPalindrome_util (int num, int revNum) throws Exception { //condizione di base; return if num=0 if (num == 0) { return revNum; } else { //callfunzione di utilità ricorsiva revNum = isPalindrome_util(num / 10, revNum); } // Verifica se la prima cifra di num e revNum sono uguali if (num % 10 == revNum % 10) { // se sì, revNum si sposterà con num return revNum / 10; } else { // exit throw new Exception(); } } //metodo per verificare se un dato numero è palindromo utilizzando la funzione di utilità palindromo public static int isPalindrome(int num) throwsException { if (num <0) num = (-num); int revNum = (num); return isPalindrome_util(num, revNum); } public static void main(String args[]) { int n = 1242; try { isPalindrome(n); System.out.println("Sì, il numero dato " + n + " è un palindromo."); } catch (Exception e) { System.out.println("No, il numero dato " + n + " non è un palindromo."); } n = 1221; try { isPalindrome(n);System.out.println("Sì, il numero dato " + n + " è palindromo"); } catch (Exception e) { System.out.println("No, il numero dato " + n + " non è palindromo"); } } } } Uscita
#3) Ricorsione inversa delle stringhe Java
Data una stringa "Hello", dobbiamo invertirla in modo che la stringa risultante sia "olleH".
A partire dall'ultimo carattere della stringa, stampiamo ricorsivamente ogni carattere fino a esaurire tutti i caratteri della stringa.
Il programma seguente utilizza la ricorsione per invertire una stringa data.
class String_Reverse { //metodo ricorsivo per invertire una stringa data void reverseString(String str) { //condizione di base; restituire se la stringa è nulla o con 1 o meno caratteri if ((str==null)} } class Main{ public static void main(String[] args) { String inputstr = "SoftwareTestingHelp"; System.out.println("La stringa data: " + inputstr); String_Reverse obj = new String_Reverse(); System.out.print("La stringa invertita: "); obj.reverseString(inputstr); } } Uscita
#4) Ricerca binaria Ricorsione Java
L'algoritmo di ricerca binaria è un famoso algoritmo di ricerca. In questo algoritmo, dato un array ordinato di n elementi, si cerca in questo array l'elemento chiave dato. All'inizio, si divide l'array in due metà trovando l'elemento centrale dell'array.
Quindi, a seconda che si tratti della metà della chiave, limitiamo la ricerca nella prima o nella seconda metà dell'array. In questo modo, lo stesso processo viene ripetuto fino a trovare la posizione degli elementi chiave.
In questa sede implementeremo questo algoritmo utilizzando la ricorsione.
import java.util.*; class Binary_Search { // ricerca binaria ricorsiva int binarySearch(int numArray[], int left, int right, int key) { if (right>= left) { //calcolare la metà dell'array int mid = left + (right - left) / 2; // se la chiave si trova a metà, restituire mid if (numArray[mid] == key) restituire mid; // se key) restituire binarySearch(numArray, left, mid - 1, key); // Altrimenti cercare ricorsivamente nell'arraysubarray destro return binarySearch(numArray, mid + 1, right, key); } // nessun elemento nell'array, return -1 return -1; } } class Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search(); //dichiara e stampa l'array int numArray[] = { 4,6,12,16,22}; System.out.println("L'array dato : " + Arrays.toString(numArray)); int len = numArray.length; //lunghezza dell'arrayint key = 16; //chiave da ricercare int result = ob.binarySearch(numArray, 0, len - 1, key); if (result == -1) System.out.println("Elemento " + key + " non presente"); else System.out.println("Elemento " + key + " trovato all'indice " + result); } } Uscita
#5) Trovare il valore minimo in una matrice usando la ricorsione
Utilizzando la ricorsione possiamo anche trovare il valore minimo della matrice.
Di seguito è riportato il programma Java per trovare il valore minimo dell'array.
import java.util.*; class Main { static int getMin(int numArray[], int i, int n) { //restituisce il primo elemento se solo un elemento o il minimo degli elementi dell'array return (n == 1) ? numArray[i] : Math.min(numArray[i], getMin(numArray,i + 1 , n - 1)); } public static void main(String[] args) { int numArray[] = { 7,32,64,2,10,23 }; System.out.println("Array dato : " + Arrays.toString(numArray)); int n =numArray.length; System.out.print("Elemento minimo dell'array: " + getMin(numArray, 0, n) + "án"); } } Uscita
Questi sono alcuni esempi di ricorsione. Oltre a questi esempi, molti altri problemi del software possono essere implementati utilizzando tecniche ricorsive.
Tipi di ricorsione
La ricorsione è di due tipi, a seconda del momento in cui viene effettuata la chiamata al metodo ricorsivo.
Essi sono:
#1) Ricorsione di coda
Quando la chiamata al metodo ricorsivo è l'ultima istruzione eseguita all'interno del metodo ricorsivo, si parla di "Tail Recursion".
Nella ricorsione di coda, l'istruzione di chiamata ricorsiva viene solitamente eseguita insieme all'istruzione di ritorno del metodo.
La sintassi generale della ricorsione di coda è riportata di seguito:
methodName ( T parameters...){ { if (base_condition == true) { return result; } return methodName (T parameters ...) //tail recursion } #2) Ricorsione della testa
La ricorsione di testa è qualsiasi approccio ricorsivo che non sia una ricorsione di coda. Quindi anche la ricorsione generale è una ricorsione di testa.
La sintassi della ricorsione di testa è la seguente:
methodName (T parameters...){ if (some_condition == true) { return methodName (T parameters...); } return result; } Ricorsione e iterazione in Java
| Ricorsione | Iterazione |
|---|---|
| La ricorsione è un processo in cui un metodo si richiama ripetutamente finché non viene soddisfatta una condizione di base. | L'iterazione è un processo in cui un pezzo di codice viene eseguito ripetutamente per un numero finito di volte o finché non viene soddisfatta una condizione. |
| È l'applicazione per le funzioni. | È applicabile ai loop. |
| Funziona bene per codici di dimensioni ridotte. | Funziona bene per codici di dimensioni maggiori. |
| Utilizza più memoria, poiché ogni chiamata ricorsiva viene inserita nello stack. | Il consumo di memoria è relativamente ridotto. |
| Difficoltà di debug e manutenzione | Più facile il debug e la manutenzione |
| Si verifica un overflow dello stack se la condizione di base non è specificata o non viene raggiunta. | Può essere eseguito all'infinito, ma alla fine interromperà l'esecuzione in caso di errori di memoria. |
| La complessità temporale è molto elevata. | La complessità temporale è relativamente bassa. |
Domande frequenti
D #1) Come funziona la ricorsione in Java?
Risposta: Nella ricorsione, la funzione ricorsiva chiama se stessa ripetutamente fino a quando non viene soddisfatta una condizione di base. La memoria della funzione chiamata viene inserita nello stack in cima alla memoria della funzione chiamante. Per ogni chiamata di funzione, viene fatta una copia separata delle variabili locali.
Q #2) Perché si usa la ricorsione?
Risposta: La ricorsione viene utilizzata per risolvere quei problemi che possono essere scomposti in altri più piccoli e l'intero problema può essere espresso in termini di un problema più piccolo.
La ricorsione viene utilizzata anche per quei problemi troppo complessi per essere risolti con un approccio iterativo. Oltre ai problemi per i quali la complessità temporale non è un problema, si può utilizzare la ricorsione.
Q #3) Quali sono i vantaggi della ricorsione?
Risposta:
I vantaggi della ricorsione includono:
- La ricorsione riduce le chiamate ridondanti di funzioni.
- La ricorsione ci permette di risolvere facilmente i problemi rispetto all'approccio iterativo.
D #4) Qual è la soluzione migliore: la ricorsione o l'iterazione?
Risposta: La ricorsione effettua chiamate ripetute fino a quando non viene raggiunta la funzione di base, quindi c'è un sovraccarico di memoria, poiché per ogni chiamata di funzione viene inserita una memoria nello stack.
L'iterazione, invece, non ha un grande overhead di memoria. L'esecuzione in ricorsione è più lenta rispetto all'approccio iterativo. La ricorsione riduce le dimensioni del codice, mentre l'approccio iterativo lo rende più grande.
Q #5) Quali sono i vantaggi della ricorsione rispetto all'iterazione?
Risposta:
- La ricorsione rende il codice più chiaro e più breve.
- La ricorsione è migliore dell'approccio iterativo per problemi come la Torre di Hanoi, le traversate ad albero, ecc.
- Poiché ogni chiamata di funzione comporta l'inserimento di memoria nello stack, la ricorsione utilizza più memoria.
- Le prestazioni della ricorsione sono più lente rispetto all'approccio iterativo.
Conclusione
La ricorsione è un concetto molto importante nel software, indipendentemente dal linguaggio di programmazione. La ricorsione viene utilizzata soprattutto per risolvere problemi di struttura di dati come le torri di Hanoi, le traversate ad albero, le liste collegate, ecc.
In questo tutorial abbiamo approfondito il tema della ricorsione e abbiamo implementato numerosi esempi di programmazione per una migliore comprensione del concetto.