Acest tutorial aprofundat despre Recursiune în Java explică ce este Recursiunea cu exemple, tipuri și concepte conexe. De asemenea, acoperă Recursiunea vs Iterarea:
În tutorialele noastre anterioare în Java, am văzut abordarea iterativă în care declarăm o buclă și apoi parcurgem o structură de date într-un mod iterativ, luând câte un element pe rând.
Am văzut, de asemenea, fluxul condițional în care păstrăm 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 apelurile de funcții, am explorat și abordarea iterativă pentru apelurile de funcții.
În acest tutorial, vom discuta o abordare diferită a programării, și anume abordarea recursivă.
Ce este recursiunea în Java?
Recursivitatea este un proces prin care o funcție sau o metodă se apelează pe ea însăși din nou și din nou. Această funcție care este apelată din nou și din nou, fie direct, fie indirect, se numește "funcție recursivă".
Vom vedea diverse exemple pentru a înțelege recursivitatea. Acum să vedem sintaxa recursivității.
Sintaxa de recurență
Orice metodă care implementează Recursiunea are două părți de bază:
- Apel de metodă care se poate apela pe sine, adică recursiv
- O precondiție care va opri recurența.
Rețineți că o precondiție este necesară pentru orice metodă recursivă, deoarece, dacă nu întrerupem recursivitatea, aceasta va continua să ruleze la infinit și va duce la o depășire a stivei.
Sintaxa generală a recursivității este următoarea:
numemetodă (T parametri...) { if (precondiție == true) //precondiție sau condiție de bază { return rezultat; } return numemetodă (T parametri...); //apel recursiv } Rețineți că precondiția se mai numește și condiție de bază. Vom discuta mai multe despre condiția de bază în secțiunea următoare.
Înțelegerea recursiunii în Java
În această secțiune, vom încerca să înțelegem procesul de recursivitate și să vedem cum are loc. Vom învăța despre condiția de bază, depășirea stivei și vom vedea cum o anumită problemă poate fi rezolvată cu recursivitate și alte detalii de acest gen.
Recursiune Condiție de bază
În timpul scrierii programului recursiv, ar trebui să furnizăm mai întâi soluția pentru cazul de bază. Apoi, vom exprima problema mai mare în termeni de probleme mai mici.
În calitate de exemplu, putem lua o problemă clasică de calcul al factorialei unui număr. Dat fiind un număr n, trebuie să găsim o factorială a lui 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) // condiție de bază 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) este condiția de bază și când această condiție este atinsă, funcția returnează 1. Partea else a funcției este apelul recursiv. Dar de fiecare dată când este apelată metoda recursivă, n este decrementat cu 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 satisface condiția de bază.
Rezolvarea problemelor folosind recursiunea
Ideea de bază din spatele utilizării recursivității este de a exprima o problemă mai mare în termeni de probleme mai mici. De asemenea, trebuie să adăugăm una sau mai multe condiții de bază pentru a putea 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), astfel încât, atunci când n ajunge la 1, putem renunța la metoda recursivă.
Eroare Stack Overflow în recursiune
Suntem conștienți de faptul că, atunci când orice metodă sau funcție este apelată, starea funcției este stocată pe stivă și este recuperată atunci când funcția se întoarce. 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 dacă condiția de bază nu este cumva atinsă sau executată. În acest caz, se poate produce o depășire a stivei.
Să luăm în considerare exemplul de mai jos de notație factorială.
Aici am dat o condiție de bază greșită, n==100.
public class Main { static int fact(int n) { if (n == 100) // condiție de bază care duce la depășirea stivei return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } } } Astfel, când n> 100, metoda va returna 1, dar recursivitatea nu se va opri. Valoarea lui n va continua să scadă 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 va umple.
Un alt caz va fi atunci când valoarea lui n <100. În acest caz, de asemenea, metoda nu va executa niciodată condiția de bază și va avea ca rezultat o depășire a stivei.
Exemple de recursiune în Java
În această secțiune, vom implementa următoarele exemple folosind recursivitatea.
#1) Seria Fibonacci folosind recursiunea
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 acesta este dat de suma dintre (n-1) și (n-2). Deoarece elementul curent este exprimat în funcție de elementele anterioare, putem exprima această problemă folosind recursivitatea.
Programul de implementare a seriei Fibonacci este prezentat mai jos:
public class Main { //metoda de calcul a seriei 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; //imprimă primele 10 numere din seria fibonacci System.out.println ("Seria Fibonacci: Primele 10 numere:"); 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 recursiunea
Un palindrom este o secvență care este egală atunci când o citim de la stânga la dreapta sau de la dreapta la stânga.
Dat fiind 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, iar când îl citim de la dreapta la stânga este 2421. Prin urmare, acesta nu este un palindrom.
Implementăm programul palindromului prin inversarea cifrelor numerelor și prin compararea recursivă a numărului dat cu reprezentarea sa inversată.
Programul de mai jos implementează programul de verificare a palindromului.
import java.io.*; import java.util.*; public class Main { // verifică dacă num conține doar o singură cifră public static int oneDigit(int num) { if ((num>= 0) && (num <10)) return 1; else return 0; } //funcție utilitară de palindrom public static public static int isPalindrome_util (int num, int revNum) throws Exception { //condiție de bază; return if num=0 if (num == 0) { return revNum; } else { //apelarefuncție utilitară recursiv revNum = isPalindrome_util(num / 10, revNum); } // Verificați dacă prima cifră din num și revNum sunt egale if (num % 10 == revNum % 10) { // dacă da, revNum se va muta cu num return revNum / 10; } else { // exit aruncă o nouă excepție(); } } } //metodă pentru a verifica dacă un număr dat este palindrom folosind funcția utilitară palindrom public static int isPalindrome(int num) aruncă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("Da, numărul dat " + n + " este un palindrom."); } catch (Exception e) { System.out.println("Nu, numărul dat " + n + " nu este un palindrom."); } n = 1221; try { isPalindrome(n);System.out.println("Da, numărul dat " + n + " este un palindrom."); } } catch (Exception e) { System.out.println("Nu, numărul dat " + n + " nu este un palindrom."); } } } } Ieșire
#3) Reverse String Recursion Java
Dat fiind un șir de caractere "Hello", trebuie să îl inversăm astfel încât șirul rezultat să fie "olleH".
Acest lucru se face prin recursivitate. Începând cu ultimul caracter din șirul de caractere, imprimăm recursiv fiecare caracter până când toate caracterele din șir sunt epuizate.
Programul de mai jos utilizează recursivitatea pentru a inversa un șir de caractere dat.
class String_Reverse { //metodă recursivă pentru a inversa un șir dat void reverseString(String str) { //condiție de bază; returnează dacă șirul este nul sau cu 1 sau mai puțin de 1 caracter if ((str==null)} } } } class Main{ public static void main(String[] args) { String inputstr = "SoftwareTestingHelp"; System.out.println("Șirul dat: " + inputstr); String_Reverse obj = new String_Reverse(); System.out.print("Șirul inversat: "); obj.reverseString(inputstr); } } } Ieșire
#4) Căutare binară Recursivitate Java
Algoritmul de căutare binară este un algoritm celebru de căutare. În acest algoritm, având în vedere un tablou sortat de n elemente, căutăm în acest tablou elementul cheie dat. La început, împărțim tabloul în două jumătăți prin găsirea elementului din mijlocul tabloului.
Apoi, în funcție de faptul dacă este vorba de 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.
import java.util.*; class Binary_Search { // căutare binară recursivă int binarySearch(int numArray[], int left, int right, int key) { if (right>= left) { //calculează mijlocul tabloului int mid = left + (right - left) / 2; // dacă cheia se află la mijlocul tabloului, returnează mid if (numArray[mid] == key) return mid; // dacă cheia cheie) return binarySearch(numArray, left, mid - 1, key); // În rest, caută recursiv în tabloulright subarray return binary_Search(numArray, mid + 1, right, key); } // nu există elemente în array, return -1 return -1; } } } class Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search(); //declară și tipărește array-ul int numArray[] = { 4,6,12,12,16,22}; System.out.println("The given array : " + Arrays.toString(numArray)); int len = numArray.length; //lungimea array-uluiint key = 16; //cheie de căutat int result = ob.binarySearch(numArray, 0, len - 1, key); if (result == -1) System.out.println("Element " + key + " nu este prezent"); else System.out.println("Element " + key + " găsit la indexul " + result); } } Ieșire
#5) Găsiți valoarea minimă în matrice folosind recursiunea
Utilizând recursivitatea, putem găsi și valoarea minimă din matrice.
Programul Java pentru a găsi valoarea minimă din matrice este prezentat mai jos.
import java.util.*; class Main { static int getMin(int numArray[], int i, int n) { //returnează primul element dacă este un singur element sau minimul elementelor din tablou 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 dat : " + Arrays.toString(numArray)); int n =numArray.length; System.out.print("Elementul minim al tabloului: " + getMin(numArray, 0, n) + "\n"); } } Ieșire
Acestea sunt câteva dintre exemplele de recursivitate. În afară de aceste exemple, multe alte probleme din software pot fi implementate folosind tehnici recursive.
Tipuri de recurență
Recursivitatea este de două tipuri, în funcție de momentul în care se face apelul la metoda recursivă.
Acestea sunt:
#1) Recursivitatea cozii
Atunci când apelul la metoda recursivă este ultima instrucțiune executată în cadrul metodei recursive, aceasta se numește "Recursiune de coadă".
În cazul recursivității de coadă, instrucțiunea de apelare recursivă este executată, de obicei, împreună cu instrucțiunea de returnare a metodei.
Sintaxa generală pentru recursivitatea cozii este prezentată mai jos:
numemetodă ( T parametri...){ { if (condiție_de_bază == true) { return rezultat; } return numemetodă (T parametri...) //recursivitate de coadă } #2) Recursivitatea capului
Recursivitatea capului este orice abordare recursivă care nu este o recursivitate de coadă. Astfel, chiar și recursivitatea generală este o recursivitate înainte.
Sintaxa recursivității capului este următoarea:
numemetodă (T parametri...){ if (some_condition == true) { return numemetodă (T parametri...); } return rezultat; } Recursiune Vs Iterare în Java
| Recursiune | Iterare |
|---|---|
| Recursivitatea este un proces prin care o metodă se apelează pe sine în mod repetat până când o condiție de bază este îndeplinită. | Iterarea este un proces prin care o bucată de cod este executată în mod repetat de un număr finit de ori sau până când o condiție este îndeplinită. |
| Este aplicația pentru funcții. | Se aplică pentru bucle. |
| Funcționează bine pentru coduri de dimensiuni mai mici. | Funcționează bine pentru coduri de dimensiuni mai mari. |
| Utilizează mai multă memorie, deoarece fiecare apel recursiv este împins în stivă. | Comparativ, se utilizează mai puțină memorie. |
| Dificil de depanat și de întreținut | Mai ușor de depanat și de întreținut |
| Are ca rezultat o depășire a 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 execuția în cazul unor erori de memorie |
| Complexitatea timpului este foarte mare. | Complexitatea timpului este relativ scăzută. |
Întrebări frecvente
Î #1) Cum funcționează Recursiunea în Java?
Răspuns: În recursivitate, funcția recursivă se apelează pe sine în mod repetat până când este îndeplinită o condiție de bază. Memoria pentru funcția apelată este împinsă pe stivă în partea de sus a memoriei pentru funcția apelantă. 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 împărțite în probleme mai mici, iar întreaga problemă poate fi exprimată în termenii unei probleme mai mici.
Recursivitatea este, de asemenea, utilizată pentru acele probleme care sunt prea complexe pentru a fi rezolvate folosind o abordare iterativă. În afară de problemele pentru care complexitatea timpului nu este o problemă, utilizați recursivitatea.
Q #3) Care sunt beneficiile recursiunii?
Răspuns:
Beneficiile recursiunii includ:
- Recursivitatea reduce apelarea redundantă a funcției.
- Recursiunea ne permite să rezolvăm problemele cu ușurință în comparație cu abordarea iterativă.
Î #4) Care dintre ele este mai bună - Recursiunea sau Iterarea?
Răspuns: Recursivitatea face apeluri repetate până când se ajunge la funcția de bază. Astfel, există o supraîncărcare a memoriei, deoarece o memorie pentru fiecare apel de funcție este pusă pe stivă.
Iterarea, pe de altă parte, nu are un mare consum de memorie. Executarea prin recursivitate este mai lentă decât abordarea iterativă. Recursivitatea reduce dimensiunea codului, în timp ce abordarea iterativă face codul mai mare.
Q #5) Care sunt avantajele recursiunii față de iterație?
Răspuns:
- Recursiunea face codul mai clar și mai scurt.
- Recursiunea este mai bună decât abordarea iterativă pentru probleme precum Turnul din Hanoi, traversarea arborilor etc.
- Deoarece fiecare apel de funcție are memorie împinsă în stivă, recursiunea utilizează mai multă memorie.
- Performanța recurenței este mai lentă decât cea a abordării iterative.
Concluzie
Recursivitatea este un concept foarte important în software, indiferent de limbajul de programare. Recursivitatea este utilizată în principal în rezolvarea problemelor de structură de date, cum ar fi turnurile din Hanoi, traversarea arborilor, listele legate etc. Deși necesită mai multă memorie, recursivitatea face codul mai simplu și mai clar.
În acest tutorial am explorat totul despre recursiune și am implementat numeroase exemple de programare pentru o mai bună înțelegere a conceptului.