recursion java tutorial with examples
Acest tutorial detaliat privind recursiunea în Java explică ce este recursiunea cu exemple, tipuri și concepte conexe. Acoperă, de asemenea, recursiunea împotriva iterației:
Din tutorialele noastre anterioare din Java, am văzut abordarea iterativă în care declarăm o buclă și apoi traversăm o structură de date într-o manieră iterativă luând câte un element la un moment dat.
De asemenea, am văzut fluxul condițional în care păstrăm din nou o variabilă de buclă și repetăm o bucată de cod până când variabila de buclă îndeplinește condiția. Când vine vorba de apeluri funcționale, am explorat abordarea iterativă și pentru apelurile funcționale.
=> Verificați TOATE Tutorialele Java aici.
În acest tutorial, vom discuta o abordare diferită a programării, adică abordarea recursivă.
Ce veți învăța:
- Ce este recursivitatea în Java?
- Recursie Vs Ierație În Java
- Concluzie
Ce este recursivitatea în Java?
Recursivitatea este un proces prin care o funcție sau o metodă se numește din nou și din nou. Această funcție care este numită din nou și din nou, direct sau indirect, este numită „funcție recursivă”.
Vom vedea diverse exemple pentru a înțelege recursivitatea. Acum să vedem sintaxa recursivității.
Sintaxă recursivă
Orice metodă care implementează recursivitatea are două părți de bază:
- Apel metodic care se poate numi singur, adică recursiv
- O condiție prealabilă care va opri recursiunea.
Rețineți că este necesară o precondiție pentru orice metodă recursivă, deoarece, dacă nu rupem recursivitatea, aceasta va continua să ruleze la infinit și va avea ca rezultat o revărsare a stivei.
Sintaxa generală a recursivității este următoarea:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } Rețineți că precondiția se mai numește și condiție de bază. Vom discuta mai multe despre starea de bază în secțiunea următoare.
Înțelegerea recursivității în Java
În această secțiune, vom încerca să înțelegem procesul de recursivitate și să vedem cum se desfășoară. Vom afla despre starea de bază, depășirea stivei și vom vedea cum o anumită problemă poate fi rezolvată prin recursivitate și alte astfel de detalii.
Starea bazei recursive
În timp ce scriem programul recursiv, ar trebui mai întâi să oferim soluția pentru cazul de bază. Apoi exprimăm problema mai mare în termeni de probleme mai mici.
cum se deschide fereastra fișierului bin
Ca un exemplu, putem lua o problemă clasică de calcul al factorialului unui număr. Având în vedere un număr n, trebuie să găsim un factorial de n notat cu n!
Acum să implementăm programul pentru a calcula factorialul n (n!) Folosind recursivitatea.
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); } }Ieșire
În acest program, putem vedea că condiția (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.
Astfel putem concluziona că în cele din urmă valoarea lui n va deveni 1 sau mai mică decât 1 și în acest moment, metoda va returna valoarea 1. Această condiție de bază va fi atinsă și funcția se va opri. Rețineți că valoarea lui n poate fi orice atâta timp cât îndeplinește condiția de bază.
Rezolvarea problemelor folosind recursivitatea
Ideea de bază din spatele utilizării recursivității este de a exprima problema mai mare în termeni de probleme mai mici. De asemenea, trebuie să adăugăm una sau mai multe condiții de bază, astfel încât să putem ieși din recursivitate.
Acest lucru a fost deja demonstrat în exemplul factorial de mai sus. În acest program, am exprimat factorialul n (n!) În termeni de valori mai mici și am avut o condiție de bază (n<=1) so that when n reaches 1, we can quit the recursive method.
Stack Overflow Error In Recursion
Suntem conștienți de faptul că atunci când se apelează orice metodă sau funcție, starea funcției este stocată în stivă și este recuperată la revenirea funcției. Stiva este utilizată și pentru metoda recursivă.
Dar în cazul recursivității, ar putea apărea o problemă dacă nu definim condiția de bază sau când condiția de bază nu este cumva atinsă sau executată. Dacă apare această situație, atunci poate apărea revărsarea stivei.
Să luăm în considerare exemplul de mai jos al notației factoriale.
Aici am dat o condiție de bază greșită, 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); } }Deci, când n> 100 metoda va reveni 1, dar recursivitatea nu se va opri. Valoarea lui n va continua să decrementeze la nesfârșit, deoarece nu există nicio altă condiție care să o oprească. Acest lucru va continua până când stiva se revarsă.
Un alt caz va fi atunci când valoarea lui n<100. In this case, as well the method will never execute the base condition and result in a stack overflow.
Exemple de recursivitate în Java
În această secțiune, vom implementa următoarele exemple folosind recursivitatea.
# 1) Seria Fibonacci folosind recursivitate
Seria Fibonacci este dată de,
1,1,2,3,5,8,13,21,34,55, ...
Secvența de mai sus arată că elementul curent este suma celor două elemente anterioare. De asemenea, primul element din seria Fibonacci este 1.
Deci, în general, dacă n este numărul curent, atunci este dat de suma dintre (n-1) și (n-2). Deoarece elementul actual este exprimat în termeni de elemente anterioare, putem exprima această problemă folosind recursivitatea.
Programul pentru implementarea seriei Fibonacci este dat mai jos:
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) + ' '); } } } Ieșire
# 2) Verificați dacă un număr este un palindrom folosind recursivitate
Un palindrom este o secvență care este egală atunci când îl citim de la stânga la dreapta sau de la dreapta la stânga.
Având un număr 121, vedem că atunci când îl citim de la stânga la dreapta și de la dreapta la stânga, este egal. Prin urmare, numărul 121 este un palindrom.
Să luăm un alt număr, 1242. Când îl citim de la stânga la dreapta este 1242 și când citim de la dreapta la stânga se citește ca 2421. Astfel, acesta nu este un palindrom.
Implementăm programul palindrom inversând cifrele numerelor și comparăm recursiv numărul dat cu reprezentarea sa inversată.
Programul de mai jos implementează programul pentru a verifica palindromul.
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.'); } } }Ieșire
# 3) Recursivitate de șir invers Java
Având un șir „Bună ziua” trebuie să-l inversăm astfel încât șirul rezultat să fie „olleH”.
Acest lucru se face folosind recursivitatea. Începând de la ultimul caracter din șir, imprimăm recursiv fiecare caracter până când toate caracterele din șir sunt epuizate.
Programul de mai jos folosește recursivitatea pentru a inversa un șir dat.
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); } } Ieșire
# 4) Căutare binară Java Recursivitate
Un algoritm de căutare binară este un algoritm celebru pentru căutare. În acest algoritm, având în vedere o matrice sortată de n elemente, căutăm în această matrice elementul cheie dat. La început, împărțim matricea în două jumătăți găsind elementul mijlociu al matricei.
Apoi, în funcție de faptul că mijlocul cheii ne limităm căutarea în prima sau a doua jumătate a matricei. În acest fel, același proces se repetă până când se găsește locația elementelor cheie.
Vom implementa acest algoritm folosind recursivitatea aici.
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); } } Ieșire
# 5) Găsiți valoarea minimă în matrice folosind recursivitate
Folosind recursivitatea putem găsi, de asemenea, valoarea minimă în matrice.
Programul Java pentru a găsi valoarea minimă în matrice este dat mai jos.
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) + '
'); } }Ieșire
Acestea sunt câteva dintre exemplele de recursivitate. În afară de aceste exemple, o mulțime de alte probleme din software pot fi implementate folosind tehnici recursive.
Tipuri de recursivitate
Recursivitatea este de două tipuri, în funcție de momentul în care se efectuează apelul către metoda recursivă.
Sunt:
# 1) Recursiunea cozii
Când apelul către metoda recursivă este ultima instrucțiune executată în interiorul metodei recursive, aceasta se numește „Recursie de coadă”.
În recursiunea de coadă, instrucțiunea de apel recursiv este de obicei executată împreună cu declarația de returnare a metodei.
Sintaxa generală pentru recursiunea cozii este dată mai jos:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } # 2) Recursivitatea capului
Recursivitatea capului este orice abordare recursivă care nu este o recursivitate a cozii. Deci, chiar și recursivitatea generală este recursivitatea înainte.
Sintaxa recursivității capului este următoarea:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } Recursie Vs Ierație În Java
| Recursivitate | Repetare |
|---|---|
| Complexitatea timpului este foarte mare. | Complexitatea timpului este relativ pe partea inferioară. |
| Recursivitatea este un proces în care o metodă se numește în mod repetat până când se îndeplinește o condiție de bază. | Iterarea este un proces prin care o bucată de cod este executată în mod repetat pentru un număr finit de ori sau până când este îndeplinită o condiție. |
| Este aplicația pentru funcții. | Se aplică buclelor. |
| Funcționează bine pentru coduri mai mici. | Funcționează bine pentru coduri mai mari. |
| Utilizează mai multă memorie pe măsură ce fiecare apel recursiv este împins în stivă | Se utilizează relativ mai puțină memorie. |
| Greu de depanat și de întreținut | Mai ușor de depanat și întreținut |
| Rezultă depășirea stivei dacă condiția de bază nu este specificată sau nu este atinsă. | Se poate executa la infinit, dar în cele din urmă va opri executarea cu orice erori de memorie |
întrebări frecvente
Q # 1) Cum funcționează recursivitatea în Java?
Răspuns: În recursivitate, funcția recursivă se apelează în mod repetat până când se îndeplinește o condiție de bază. Memoria pentru funcția apelată este împinsă în stiva din partea de sus a memoriei pentru funcția de apelare. Pentru fiecare apel de funcție, se face o copie separată a variabilelor locale.
Q # 2) De ce se folosește recursivitatea?
Răspuns: Recursivitatea este utilizată pentru a rezolva acele probleme care pot fi defalcate în altele mai mici și întreaga problemă poate fi exprimată în termeni de problemă mai mică.
Recursivitatea este, de asemenea, utilizată pentru acele probleme care sunt prea complexe pentru a fi rezolvate folosind o abordare iterativă. Pe lângă problemele pentru care complexitatea timpului nu este o problemă, utilizați recursivitatea.
Q # 3) Care sunt beneficiile recursiunii?
Răspuns:
Beneficiile recursivității includ:
- Recursivitatea reduce apelarea redundantă a funcției.
- Recursivitatea ne permite să rezolvăm problemele cu ușurință în comparație cu abordarea iterativă.
Q # 4) Care este mai bun - recursivitate sau iterație?
Răspuns: Recursiunea efectuează apeluri repetate până când funcția de bază este atinsă. Astfel, există o cheltuială de memorie, deoarece o memorie pentru fiecare apel funcțional este împinsă în stivă.
Pe de altă parte, iterația nu are prea multă memorie. Execuția recursivă este mai lentă decât abordarea iterativă. Recursivitatea reduce dimensiunea codului, în timp ce abordarea iterativă face codul mare.
Q # 5) Care sunt avantajele recursivității față de iterație?
Răspuns:
- Recursivitatea face codul mai clar și mai scurt.
- Recursivitatea este mai bună decât abordarea iterativă pentru probleme precum Turnul din Hanoi, traversarea copacilor etc.
- Deoarece fiecare apel funcțional are memorie împinsă în stivă, Recursion folosește mai multă memorie.
- Performanța recursivă este mai lentă decât abordarea iterativă.
Concluzie
Recursivitatea este un concept foarte important în software, indiferent de limbajul de programare. Recursivitatea este folosită mai ales în rezolvarea problemelor de structură a datelor, cum ar fi turnurile din Hanoi, traversarea copacilor, listele legate, etc.
Am explorat totul despre recursivitate în acest tutorial. De asemenea, am implementat numeroase exemple de programare pentru o mai bună înțelegere a conceptului.
=> Citiți seria Easy Training Java.
Lectură recomandată
- Recursivitate în C ++
- Java Iterator: Aflați cum să utilizați Iterators în Java cu exemple
- Interfață ListIterator în Java cu exemple
- Tutorial JAVA pentru începători: peste 100 de cursuri video Java practice
- Tutorial Java For Loop cu exemple de programe
- Java While Loop - Tutorial cu exemple de programare
- Java Do While Loop - Tutorial cu exemple
- Matrice Jagged în Java - Tutorial cu exemple