...
← Blog Lecții programare java

Recursivitatea în Java: metode recursive explicate cu exemple

Sigla Java, ilustrație pentru lecția despre recursivitatea în Java

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.

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.

ParteaCe faceÎn exemplul de mai sus
Cazul de bazăreturnează direct un rezultat, fără alt apel recursivif (n == 0) afișează „Start!” și iese
Pasul recursivapelează metoda cu o problemă mai micănumaraInvers(n - 1)
Progresulgarantează 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):

  1. factorial(5) are nevoie de factorial(4) și așteaptă;
  2. factorial(4) are nevoie de factorial(3) și așteaptă;
  3. la fel pentru 3 și 2, până la factorial(1), care returnează direct 1;
  4. 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.

CriteriuRecursivitateBuclă (for, while)
Memorieun cadru pe stivă pentru fiecare apelconstantă, câteva variabile
Risc la date mariStackOverflowErrorniciunul de acest tip
Claritate la arbori, foldere, meniurifoarte bunăcodul devine mai lung, cu o stivă ținută manual
Claritate la sume și numărătoribună, dar fără avantajla 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:

  1. Lipsește cazul de bază. Metoda se apelează la nesfârșit și programul se oprește cu StackOverflowError.
  2. Parametrul nu se apropie de cazul de bază. Scrii factorial(n) în loc de factorial(n - 1) sau n + 1 în loc de n - 1. Rezultatul e tot o recursie infinită.
  3. Cazul de bază e incomplet. if (n == 1) merge pentru 5, dar factorial(0) sau un număr negativ nu îl mai ating niciodată. De aceea exemplul folosește n <= 1 și validează valorile negative.
  4. Uiți de return. Calculezi n * factorial(n - 1), dar nu returnezi rezultatul, iar compilatorul îți semnalează că metoda nu returnează nimic pe toate ramurile.
  5. Tipul numeric e prea mic. factorial(13) cu int afișează 1932053504 în loc de 6227020800, fără nicio eroare. Pentru numere mari folosești long sau BigInteger.
  6. Folosești recursivitatea pentru orice repetare. Dacă problema e o simplă numărătoare de la 1 la n, o buclă for e 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.

Logo Curs Java Interactiv · 15 lecții gratuite

Curs Java

Programare Java pentru începători: de la sintaxă la OOP și colecții

Începe gratuit

Citește și

Primul tău program e la 5 minute distanță.

Creează-ți contul gratuit și începe primele 15 lecții. Fără card, fără instalări.

Începe gratuit