
Recursivitatea în Java înseamnă că o metodă se apelează pe ea însăși ca să rezolve o versiune mai mică a aceleiași probleme. Orice metodă recursivă are două părți: un caz de bază, care oprește apelurile, și un pas recursiv, care micșorează problema până ajunge la cazul de bază. Fără cazul de bază, programul se oprește cu StackOverflowError.
Dacă vrei să înveți practic, curs Java online are primele lecții gratuite, cu exerciții verificate direct în browser.
Recursivitatea explicată cu animație, în Java, C++ și Python: recursivitate: cazul de bază și stiva de apeluri și backtracking.
În lecția asta vezi cum arată o metodă recursivă, ce se întâmplă în memorie la fiecare apel, exemplele clasice (factorial, suma unui vector, palindrom, Fibonacci, căutare binară), când e mai bună o buclă și greșelile pe care le fac aproape toți începătorii.
Ce este recursivitatea în Java?
Recursivitatea este tehnica prin care o metodă își rezolvă problema apelându-se pe ea însăși cu date mai mici. Gândește-te la un teanc de 100 de facturi de numărat. Poți spune: „numărul de facturi este 1 plus numărul facturilor rămase”. Apoi repeți aceeași regulă pentru teancul rămas, până nu mai ai nicio factură. Acolo te oprești și răspunsul e 0.
Dacă ai parcurs lecția despre metode în Java, știi deja tot ce îți trebuie. O metodă recursivă e o metodă obișnuită, cu parametri și valoare returnată. Singura diferență este că, undeva în corpul ei, apare un apel către ea însăși.
Primul exemplu e o numărătoare inversă:
static void numaraInvers(int n) {
if (n == 0) { // cazul de bază
System.out.println("Start!");
return;
}
System.out.println(n);
numaraInvers(n - 1); // pasul recursiv
} Apelul numaraInvers(3) afișează 3, 2, 1 și apoi „Start!”. Fiecare apel lucrează cu un n mai mic cu 1, iar când n ajunge la 0, metoda nu se mai apelează.
Care sunt cele două părți ale unei metode recursive?
O metodă recursivă corectă are mereu un caz de bază și un pas recursiv care se apropie de el. Dacă lipsește oricare dintre ele, metoda fie nu face nimic util, fie nu se mai oprește.
| Partea | Ce face | În exemplul de mai sus |
|---|---|---|
| Cazul de bază | returnează direct un rezultat, fără alt apel recursiv | if (n == 0) afișează „Start!” și iese |
| Pasul recursiv | apelează metoda cu o problemă mai mică | numaraInvers(n - 1) |
| Progresul | garantează că, la un moment dat, ajungi la cazul de bază | n scade cu 1 la fiecare apel |
Înainte să scrii orice metodă recursivă, răspunde la două întrebări: care e cea mai mică problemă pe care o rezolv direct? Și cum transform problema actuală într-una mai mică de același fel? Dacă ai răspunsurile, codul se scrie aproape singur.
Cum funcționează call stack-ul la recursivitate?
Call stack-ul (stiva de apeluri) este zona de memorie în care Java ține evidența metodelor care rulează și a variabilelor lor locale. La fiecare apel, Java pune deasupra stivei un cadru nou, cu propria copie a parametrilor. Când metoda se termină, cadrul ei e scos, iar execuția continuă în metoda care a apelat-o.
Cel mai bine se vede pe factorial. Factorialul lui 5 (scris 5!) este 5 × 4 × 3 × 2 × 1 = 120, iar regula recursivă e simplă: n! = n × (n − 1)!, cu 1! = 1.
static int factorial(int n) {
if (n < 0) {
throw new IllegalArgumentException("n nu poate fi negativ");
}
if (n <= 1) {
return 1;
}
return n * factorial(n - 1);
} Iată ce se întâmplă la factorial(5):
factorial(5)are nevoie defactorial(4)și așteaptă;factorial(4)are nevoie defactorial(3)și așteaptă;- la fel pentru 3 și 2, până la
factorial(1), care returnează direct 1; - apoi stiva se golește în sens invers: 2 × 1 = 2, 3 × 2 = 6, 4 × 6 = 24, 5 × 24 = 120.
Observă că înmulțirile se fac la întoarcere, nu la coborâre. Aici e lucrul care îi încurcă pe începători: apelul recursiv nu „sare” la final, ci pune metoda curentă pe pauză până primește rezultatul.
Ordinea instrucțiunilor contează din același motiv. Dacă în numaraInvers muți System.out.println(n) după apelul recursiv, numerele apar în ordinea 1, 2, 3, pentru că fiecare afișare se execută abia când apelul de dedesubt s-a terminat.
De ce apare StackOverflowError?
StackOverflowError apare când stiva de apeluri se umple, de obicei pentru că metoda nu ajunge niciodată la cazul de bază. Stiva are o dimensiune limitată, iar fiecare apel ocupă un cadru. Dacă apelurile nu se mai opresc, după câteva mii de niveluri (numărul exact depinde de JVM și de setări) programul se oprește cu această eroare.
static int factorialGresit(int n) {
return n * factorialGresit(n - 1); // lipsește cazul de bază
} Același lucru se poate întâmpla și cu o metodă corectă, dacă îi dai o problemă foarte mare. O recursie cu 100.000 de niveluri poate umple stiva chiar dacă are caz de bază. De aceea, pentru volume mari de date, varianta cu buclă e mai sigură.
Exemple de metode recursive în Java
Majoritatea problemelor recursive de început urmează același tipar: rezolvi primul element și lași restul pe seama apelului recursiv. Exemplele de mai jos rulează așa cum sunt, pune-le într-o clasă și apelează-le din main.
Suma elementelor dintr-un vector
Suma unui vector este primul element plus suma restului. Ca să nu copiezi vectorul la fiecare pas, trimiți mai departe indexul de la care începi:
static int sumaArray(int[] v, int index) {
if (index == v.length) { // nu mai sunt elemente
return 0;
}
return v[index] + sumaArray(v, index + 1);
}
int[] note = {9, 10, 8, 7, 10};
System.out.println(sumaArray(note, 0)); // 44 Verificarea unui palindrom
Un palindrom se citește la fel de la ambele capete, ca „cojoc” sau „rotor”. Compari primul și ultimul caracter, apoi verifici ce rămâne la mijloc:
static boolean estePalindrom(String text) {
if (text.length() <= 1) {
return true;
}
if (text.charAt(0) != text.charAt(text.length() - 1)) {
return false;
}
return estePalindrom(text.substring(1, text.length() - 1));
}
System.out.println(estePalindrom("cojoc")); // true
System.out.println(estePalindrom("java")); // false Aici ai două cazuri de bază: textul scurt (adevărat) și o pereche de caractere diferite (fals). E perfect normal ca o metodă recursivă să aibă mai multe cazuri de bază.
Căutarea binară
Căutarea binară găsește o valoare într-un vector sortat înjumătățind la fiecare pas zona în care cauți. E exemplul în care recursivitatea se potrivește natural, pentru că fiecare pas e aceeași problemă pe o jumătate de vector:
static int cautareBinara(int[] v, int cautat, int stanga, int dreapta) {
if (stanga > dreapta) {
return -1; // nu există
}
int mijloc = stanga + (dreapta - stanga) / 2;
if (v[mijloc] == cautat) {
return mijloc;
}
if (cautat < v[mijloc]) {
return cautareBinara(v, cautat, stanga, mijloc - 1);
}
return cautareBinara(v, cautat, mijloc + 1, dreapta);
}
int[] preturi = {12, 25, 37, 49, 58, 73, 91};
System.out.println(cautareBinara(preturi, 49, 0, preturi.length - 1)); // 3 Pentru un milion de prețuri sortate, căutarea binară are nevoie de cel mult 20 de pași. Tiparul acesta apare des la interviuri, alături de alte probleme pe care le exersezi în cursul de algoritmi pentru interviuri.
Parcurgerea unui folder cu subfoldere
Structurile care conțin elemente de același tip, cum sunt folderele, meniurile cu submeniuri sau comentariile cu răspunsuri, sunt locul unde recursivitatea e cu adevărat cea mai simplă soluție:
import java.io.File;
static void afiseazaFolder(File folder, int nivel) {
File[] continut = folder.listFiles();
if (continut == null) {
return;
}
for (File f : continut) {
System.out.println(" ".repeat(nivel) + f.getName());
if (f.isDirectory()) {
afiseazaFolder(f, nivel + 1);
}
}
} Nu știi dinainte câte niveluri de subfoldere există. Cu o buclă simplă ar trebui să ții singur evidența lor, pe când recursivitatea o face pentru tine prin call stack.
De ce e lent Fibonacci recursiv și cum îl repari?
Fibonacci recursiv e lent pentru că recalculează aceleași valori de foarte multe ori. Șirul Fibonacci începe cu 0 și 1, iar fiecare termen e suma celor doi dinainte: 0, 1, 1, 2, 3, 5, 8, 13…
static long fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
} Codul e corect și arată exact ca definiția matematică. Problema e că fibonacci(5) calculează fibonacci(3) de două ori, fibonacci(2) de trei ori și așa mai departe. Numărul de apeluri crește exponențial: la fibonacci(40) sunt sute de milioane de apeluri, iar la 50 aștepți aproape un minut.
Soluția se numește memoizare: salvezi fiecare rezultat calculat și îl refolosești data viitoare.
static long fibonacciMemo(int n, long[] memo) {
if (n <= 1) {
return n;
}
if (memo[n] != 0) {
return memo[n]; // deja calculat
}
memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
return memo[n];
}
System.out.println(fibonacciMemo(50, new long[51])); // 12586269025 Acum fiecare termen se calculează o singură dată, iar rezultatul apare instantaneu. Am folosit long, nu int, pentru că al 50-lea termen nu mai încape în int.
Recursivitate sau buclă: ce alegi?
Orice metodă recursivă poate fi rescrisă cu o buclă, iar pentru calcule liniare simple (factorial, sume, numărători) bucla e de obicei alegerea mai bună în Java. Recursivitatea câștigă la structurile ierarhice și la problemele care se împart natural în subprobleme.
| Criteriu | Recursivitate | Buclă (for, while) |
|---|---|---|
| Memorie | un cadru pe stivă pentru fiecare apel | constantă, câteva variabile |
| Risc la date mari | StackOverflowError | niciunul de acest tip |
| Claritate la arbori, foldere, meniuri | foarte bună | codul devine mai lung, cu o stivă ținută manual |
| Claritate la sume și numărători | bună, dar fără avantaj | la fel de clară și mai sigură |
| Viteză | puțin mai lentă (costul apelurilor) | de obicei mai rapidă |
Un detaliu care apare la interviuri: unele limbaje transformă automat recursivitatea terminală (apelul recursiv e ultima operație) într-o buclă. Java nu face asta, așa că o recursie terminală foarte adâncă poate umple stiva la fel ca oricare alta.
Ce greșeli fac începătorii cu metodele recursive?
Aproape toate erorile cu recursivitatea vin din cazul de bază sau din felul în care se schimbă parametrul. Iată-le pe cele mai dese:
- Lipsește cazul de bază. Metoda se apelează la nesfârșit și programul se oprește cu
StackOverflowError. - Parametrul nu se apropie de cazul de bază. Scrii
factorial(n)în loc defactorial(n - 1)saun + 1în loc den - 1. Rezultatul e tot o recursie infinită. - Cazul de bază e incomplet.
if (n == 1)merge pentru 5, darfactorial(0)sau un număr negativ nu îl mai ating niciodată. De aceea exemplul foloseșten <= 1și validează valorile negative. - Uiți de
return. Calculezin * factorial(n - 1), dar nu returnezi rezultatul, iar compilatorul îți semnalează că metoda nu returnează nimic pe toate ramurile. - Tipul numeric e prea mic.
factorial(13)cuintafișează 1932053504 în loc de 6227020800, fără nicio eroare. Pentru numere mari foloseștilongsauBigInteger. - Folosești recursivitatea pentru orice repetare. Dacă problema e o simplă numărătoare de la 1 la n, o buclă
fore mai clară și nu riscă stiva.
Pentru factoriale cu adevărat mari, clasa BigInteger din java.math nu are limită de mărime:
import java.math.BigInteger;
static BigInteger factorialMare(int n) {
if (n <= 1) {
return BigInteger.ONE;
}
return BigInteger.valueOf(n).multiply(factorialMare(n - 1));
}
System.out.println(factorialMare(25)); // 15511210043330985984000000 Când o metodă recursivă nu face ce te aștepți, adaugă temporar un System.out.println la începutul ei care afișează parametrii și nivelul. Vei vedea imediat dacă parametrul scade cum trebuie sau dacă sare peste cazul de bază. Alte capcane din primele luni găsești în articolul despre greșelile frecvente ale începătorilor în Java.
Exercițiu: numărul de cifre
Scrie metoda recursivă static int numarCifre(int n), care returnează câte cifre are un număr pozitiv. Indiciu: un număr mai mic decât 10 are o cifră, iar orice alt număr are o cifră în plus față de n / 10. Pentru 2026, metoda trebuie să returneze 4.
Apoi scrie aceeași metodă cu o buclă while și compară cele două variante. Vei vedea că pentru o problemă liniară ca aceasta, ambele sunt la fel de scurte.
Întrebări frecvente
Ce este o metodă recursivă în Java?
Este o metodă care se apelează pe ea însăși, cu date mai mici, până ajunge la un caz suficient de simplu încât să îl rezolve direct. Are mereu un caz de bază și un pas recursiv.
Recursivitatea este mai rapidă decât o buclă?
Nu. În Java, fiecare apel costă timp și un cadru pe stivă, așa că bucla e de obicei puțin mai rapidă. Recursivitatea se alege pentru claritate, mai ales la structuri ierarhice.
Poate o metodă recursivă să aibă mai multe cazuri de bază?
Da. Verificarea unui palindrom are două: textul scurt și o pereche de caractere diferite. Fibonacci are, practic, două valori de pornire, 0 și 1.
Java optimizează recursivitatea terminală?
Nu. Spre deosebire de unele limbaje funcționale, Java păstrează câte un cadru pe stivă pentru fiecare apel, chiar dacă apelul recursiv e ultima operație din metodă.
Când ar trebui să evit recursivitatea?
Când adâncimea poate deveni foarte mare (zeci de mii de niveluri) sau când problema e o simplă repetare, cum ar fi o sumă de la 1 la n. În aceste cazuri, o buclă e mai sigură și la fel de clară.
Primul pas: rescrie factorialul în trei feluri
Scrie azi factorialul recursiv, apoi aceeași metodă cu for, apoi varianta cu BigInteger. Scoate intenționat cazul de bază și uită-te la mesajul StackOverflowError, ca să îl recunoști când îl întâlnești în proiectele tale.
Dacă vrei exerciții de recursivitate verificate automat, primele 15 lecții din cursul de Java sunt gratuite. Scrii codul direct în browser, fără să instalezi nimic, iar Profu’, tutorele AI din lecții, îți dă indicii când nu găsești cazul de bază. Dacă vrei să vezi tot drumul până la primul job, uită-te la traseul de Java Developer.
Lecția anterioară: metode în Java. Lecția următoare: clase și obiecte în Java.
Curs Java
Programare Java pentru începători: de la sintaxă la OOP și colecții
Începe gratuit
