recursion java tutorial with examples
Questo tutorial approfondito sulla ricorsione in Java spiega cos'è la ricorsione con esempi, tipi e concetti correlati. Copre anche la ricorsione contro l'iterazione:
Dai nostri tutorial precedenti in Java, abbiamo visto l'approccio iterativo in cui dichiariamo un ciclo e poi attraversiamo una struttura dati in modo iterativo prendendo un elemento alla volta.
Abbiamo anche visto il flusso condizionale in cui ancora una volta manteniamo una variabile di ciclo e ripetiamo un pezzo di codice finché la variabile di ciclo non soddisfa la condizione. Quando si tratta di chiamate di funzione, abbiamo esplorato l'approccio iterativo anche per le chiamate di funzione.
=> Controlla TUTTI i tutorial Java qui.
In questo tutorial, discuteremo un approccio diverso alla programmazione, ovvero l'approccio ricorsivo.
Cosa imparerai:
- Cos'è la ricorsione in Java?
- Ricorsione vs iterazione in Java
- Conclusione
Cos'è la ricorsione in Java?
La ricorsione è un processo mediante il quale una funzione o un metodo chiama se stesso più e più volte. Questa funzione che viene chiamata più e più volte direttamente o indirettamente è chiamata 'funzione ricorsiva'.
Vedremo vari esempi per comprendere la ricorsione. Vediamo ora la sintassi della ricorsione.
Sintassi della ricorsione
Qualsiasi metodo che implementa la ricorsione ha due parti fondamentali:
- Chiamata al metodo che può chiamarsi, cioè ricorsiva
- Una precondizione che fermerà la ricorsione.
Si noti che una precondizione è necessaria per qualsiasi metodo ricorsivo poiché, se non interrompiamo la ricorsione, continuerà a funzionare all'infinito e risulterà in uno stack overflow.
La sintassi generale della ricorsione è la seguente:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } Notare che la precondizione è anche chiamata condizione di base. Discuteremo di più sulla condizione di base nella prossima sezione.
Capire la ricorsione in Java
In questa sezione, proveremo a capire il processo di ricorsione e vedere come si svolge. Impareremo la condizione di base, lo stack overflow e vedremo come un particolare problema può essere risolto con la ricorsione e altri dettagli simili.
Condizione di base della ricorsione
Durante la scrittura del programma ricorsivo, dobbiamo prima fornire la soluzione per il caso base. Quindi esprimiamo 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!) Usando la ricorsione.
public class Main{ static int fact(int n) { if (n == 1) // base condition return 1; else return n*fact(n-1); } public static void main(String() args) { int result = fact(10); System.out.println('10! = ' + result); } }Produzione
In questo programma possiamo vedere che la condizione (n<=1) is the base condition and when this condition is reached, the function returns 1. The else part of the function is the recursive call. But every time the recursive method is called, n is decremented by 1.
Possiamo quindi concludere che alla fine il valore di n diventerà 1 o minore di 1 ea questo punto il metodo restituirà il valore 1. Questa condizione di base verrà raggiunta e la funzione si fermerà. Nota che il valore di n può essere qualsiasi cosa fintanto che soddisfa la condizione di base.
Risoluzione dei problemi utilizzando la ricorsione
L'idea alla base dell'uso della ricorsione è esprimere il problema più grande in termini di problemi più piccoli. Inoltre, dobbiamo aggiungere una o più condizioni di base in modo da poter uscire dalla ricorsione.
Ciò è stato già dimostrato nell'esempio fattoriale sopra. In questo programma, abbiamo espresso il fattoriale n (n!) In termini di valori più piccoli e avevamo una condizione di base (n<=1) so that when n reaches 1, we can quit the recursive method.
Errore di overflow dello stack nella ricorsione
Siamo consapevoli che quando viene chiamato un metodo o una funzione, lo stato della funzione viene memorizzato nello stack e viene recuperato quando la funzione ritorna. Lo stack viene utilizzato anche per il metodo ricorsivo.
Ma nel caso della ricorsione, potrebbe verificarsi un problema se non definiamo la condizione di base o quando la condizione di base non viene in qualche modo raggiunta o eseguita. Se si verifica questa situazione, potrebbe verificarsi l'overflow dello stack.
Consideriamo l'esempio seguente di notazione fattoriale.
Qui abbiamo dato una condizione di base errata, n == 100.
public class Main { static int fact(int n) { if (n == 100) // base condition resulting in stack overflow 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 indefinitamente poiché non ci sono altre condizioni per fermarlo. Questo andrà avanti fino all'overflow dello stack.
Un altro caso sarà quando il valore di n<100. In this case, as well the method will never execute the base condition and result in a stack overflow.
Esempi di ricorsione in Java
In questa sezione, implementeremo i seguenti esempi utilizzando la ricorsione.
# 1) Serie di Fibonacci che utilizza la ricorsione
La serie di Fibonacci è data da,
1,1,2,3,5,8,13,21,34,55, ...
La sequenza precedente 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 usando la ricorsione.
Di seguito è riportato il programma per implementare la serie di Fibonacci:
public class Main { //method to calculate fibonacci series 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; //print first 10 numbers of fibonacci series System.out.println ('Fibonacci Series: First 10 numbers:'); for (int i = 1; i <= number; i++) { System.out.print(fibonacci(i) + ' '); } } } Produzione
# 2) Controlla se un numero è un palindromo usando la ricorsione
Un palindromo è una sequenza che è uguale quando la leggiamo 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 è un palindromo.
Prendiamo un altro numero, 1242. Quando lo leggiamo da sinistra a destra è 1242 e quando leggiamo da destra a sinistra si legge come 2421. Quindi questo non è un palindromo.
Implementiamo il programma palindromo invertendo le cifre dei numeri e confrontiamo ricorsivamente il numero dato con la sua rappresentazione invertita.
Il programma seguente implementa il programma per controllare il palindromo.
import java.io.*; import java.util.*; public class Main { // check if num contains only one digit public static int oneDigit(int num) { if ((num >= 0) && (num <10)) return 1; else return 0; } //palindrome utility function public static int isPalindrome_util (int num, int revNum) throws Exception { // base condition; return if num=0 if (num == 0) { return revNum; } else { //call utility function recursively revNum = isPalindrome_util(num / 10, revNum); } // Check if first digit of num and revNum are equal if (num % 10 == revNum % 10) { // if yes, revNum will move with num return revNum / 10; } else { // exit throw new Exception(); } } //method to check if a given number is palindrome using palindrome utility function public static int isPalindrome(int num) throws Exception { 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('Yes, the given number ' + n + ' is a palindrome.'); } catch (Exception e) { System.out.println('No, the given number ' + n + ' is not a palindrome.'); } n = 1221; try { isPalindrome(n); System.out.println('Yes, the given number ' + n + ' is a palindrome.'); } catch (Exception e) { System.out.println('No, the given number ' + n + ' is not a palindrome.'); } } }Produzione
# 3) Java ricorsione inversa delle stringhe
Data una stringa 'Hello', dobbiamo invertirla in modo che la stringa risultante sia 'olleH'.
Questo viene fatto usando la ricorsione. A partire dall'ultimo carattere della stringa stampiamo ricorsivamente ogni carattere fino ad esaurimento di tutti i caratteri della stringa.
Il programma seguente utilizza la ricorsione per invertire una determinata stringa.
class String_Reverse { //recursive method to reverse a given string void reverseString(String str) { //base condition; return if string is null or with 1 or less character if ((str==null)||(str.length() <= 1)) System.out.println(str); else { //recursively print each character in the string from the end System.out.print(str.charAt(str.length()-1)); reverseString(str.substring(0,str.length()-1)); } } } class Main{ public static void main(String() args) { String inputstr = 'SoftwareTestingHelp'; System.out.println('The given string: ' + inputstr); String_Reverse obj = new String_Reverse(); System.out.print('The reversed string: '); obj.reverseString(inputstr); } } Produzione
# 4) Ricorsione Java di ricerca binaria
Un algoritmo di ricerca binaria è un famoso algoritmo per la ricerca. In questo algoritmo, dato un array ordinato di n elementi, cerchiamo questo array per l'elemento chiave specificato. All'inizio, dividiamo l'array in due metà trovando l'elemento medio dell'array.
Quindi a seconda che la chiave mid limitiamo la nostra ricerca nella prima o nella seconda metà dell'array. In questo modo viene ripetuto lo stesso processo finché non viene trovata la posizione degli elementi chiave.
Implementeremo questo algoritmo usando la ricorsione qui.
import java.util.*; class Binary_Search { // recursive binary search int binarySearch(int numArray(), int left, int right, int key) { if (right >= left) { //calculate mid of the array int mid = left + (right - left) / 2; // if the key is at mid, return mid if (numArray(mid) == key) return mid; // if key key) return binarySearch(numArray, left, mid - 1, key); // Else recursively search in the right subarray return binarySearch(numArray, mid + 1, right, key); } // no elements in the array, return -1 return -1; } } class Main{ public static void main(String args()) { Binary_Search ob = new Binary_Search(); //declare and print the array int numArray() = { 4,6,12,16,22}; System.out.println('The given array : ' + Arrays.toString(numArray)); int len = numArray.length; //length of the array int key = 16; //key to be searched int result = ob.binarySearch(numArray, 0, len - 1, key); if (result == -1) System.out.println('Element ' + key + ' not present'); else System.out.println('Element ' + key + ' found at index ' + result); } } Produzione
# 5) Trova il valore minimo in array usando la ricorsione
Usando la ricorsione possiamo anche trovare il valore minimo nell'array.
Di seguito viene fornito il programma Java per trovare il valore minimo nell'array.
import java.util.*; class Main { static int getMin(int numArray(), int i, int n) { //return first element if only one element or minimum of the array elements 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('Given Array : ' + Arrays.toString(numArray)); int n = numArray.length; System.out.print('Minimum element of array: ' + getMin(numArray, 0, n) + '
'); } }Produzione
Questi sono alcuni degli esempi di ricorsione. Oltre a questi esempi, molti altri problemi nel software possono essere implementati utilizzando tecniche ricorsive.
Tipi di ricorsione
La ricorsione è di due tipi in base a quando viene effettuata la chiamata al metodo ricorsivo.
Sono:
# 1) Ricorsione della coda
Quando la chiamata al metodo ricorsivo è l'ultima istruzione eseguita all'interno del metodo ricorsivo, si chiama “Tail Recursion”.
Nella ricorsione in coda, l'istruzione di chiamata ricorsiva viene solitamente eseguita insieme all'istruzione return del metodo.
Di seguito viene fornita la sintassi generale per la ricorsione della coda:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } # 2) Ricorsione della testa
La ricorsione della testa è un approccio ricorsivo che non sia una ricorsione della coda. Quindi anche la ricorsione generale è ricorsione in anticipo.
La sintassi della ricorsione della testa è la seguente:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } Ricorsione vs iterazione in Java
| Ricorsione | Iterazione |
|---|---|
| La complessità del tempo è molto alta. | La complessità temporale è relativamente sul lato inferiore. |
| La ricorsione è un processo in cui un metodo chiama se stesso ripetutamente finché non viene soddisfatta una condizione di base. | L'iterazione è un processo mediante il quale un pezzo di codice viene ripetutamente eseguito per un numero finito di volte o finché non viene soddisfatta una condizione. |
| È l'applicazione per le funzioni. | È applicabile per i loop. |
| Funziona bene per codice di dimensioni inferiori. | Funziona bene per codici di dimensioni maggiori. |
| Utilizza più memoria quando ogni chiamata ricorsiva viene inserita nello stack | Viene utilizzata una memoria relativamente inferiore. |
| Difficile eseguire il debug e la manutenzione | Più facile da eseguire il debug e da mantenere |
| Produce un overflow dello stack se la condizione di base non viene specificata o non viene raggiunta. | Può essere eseguito all'infinito ma alla fine interromperà l'esecuzione con eventuali errori di memoria |
Domande frequenti
D # 1) Come funziona la ricorsione in Java?
Risposta: Nella ricorsione, la funzione ricorsiva chiama se stessa ripetutamente finché una condizione di base non è soddisfatta. La memoria per la funzione chiamata viene inserita nello stack nella parte superiore della memoria per la funzione chiamante. Per ogni chiamata di funzione, viene creata una copia separata delle variabili locali.
Q # 2) Perché viene utilizzata la ricorsione?
Risposta: La ricorsione viene utilizzata per risolvere quei problemi che possono essere scomposti in problemi più piccoli e l'intero problema può essere espresso in termini di un problema più piccolo.
La ricorsione viene utilizzata anche per quei problemi che sono troppo complessi per essere risolti utilizzando un approccio iterativo. Oltre ai problemi per i quali la complessità temporale non è un problema, usa la ricorsione.
Q # 3) Quali sono i vantaggi della ricorsione?
Risposta:
I vantaggi della ricorsione includono:
domande e risposte dell'intervista del server ms sql per esperti
- La ricorsione riduce la chiamata ridondante della funzione.
- La ricorsione ci consente di risolvere facilmente i problemi rispetto all'approccio iterativo.
D # 4) Qual è il migliore: ricorsione o iterazione?
Risposta: La ricorsione effettua chiamate ripetute finché non viene raggiunta la funzione di base. Quindi c'è un sovraccarico di memoria poiché una memoria per ogni chiamata di funzione viene inserita nello stack.
L'iterazione d'altra parte non ha molto sovraccarico di memoria. L'esecuzione della ricorsione è più lenta dell'approccio iterativo. La ricorsione riduce la dimensione del codice mentre l'approccio iterativo rende il codice 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, attraversamenti di alberi, ecc.
- Poiché ogni chiamata di funzione ha memoria inserita nello stack, la ricorsione utilizza più memoria.
- Le prestazioni di ricorsione sono più lente dell'approccio iterativo.
Conclusione
La ricorsione è un concetto molto importante nel software indipendentemente dal linguaggio di programmazione. La ricorsione viene utilizzata principalmente per risolvere problemi di struttura dei dati come torri di Hanoi, attraversamenti di alberi, elenchi concatenati, ecc. Sebbene richieda più memoria, la ricorsione rende il codice più semplice e chiaro.
Abbiamo esplorato tutto sulla ricorsione in questo tutorial. Abbiamo anche implementato numerosi esempi di programmazione per una migliore comprensione del concetto.
=> Leggere attraverso la serie di formazione Easy Java.
Lettura consigliata
- Ricorsione in C ++
- Iteratore Java: impara a utilizzare gli iteratori in Java con esempi
- Interfaccia ListIterator in Java con esempi
- Tutorial JAVA per principianti: oltre 100 tutorial video Java pratici
- Tutorial Java For Loop con esempi di programmi
- Java While Loop - Tutorial con esempi di programmazione
- Java Do While Loop - Tutorial con esempi
- Jagged Array in Java - Tutorial con esempi