Remarcam că, la fel ca în cazul ciclurilor iterative, în metodele recursive trebuie să existe o condiție de oprire a repetării. În caz contrar recursia ar continua până la depășirea spațiului de memorie alocat pentru memorarea datelor intermediare (numit stivă).
Comparând metodele recursive cu cele iterative se constată că:
- metodele recursive sunt "mai elegante", fiind și mai ușor de
ințeles de către om decât cele iterative;
- din punct de vedere computațional, metodele iterative sunt mai
eficiente, deoarece solicită mai puțină memorie și sunt mai rapide decât
cele recursive. Deosebirea este cu atât mai mare, cu cât numărul de
invocari succesive, respectiv de repetări, este mai mare.
Exemplul 1:
Un exemplu tipic de funcție recursivă este calcularea factorialului. Din punct de vedere matematic, factorialul este o funcție
factorial(n) = 1*2*3*...*n
care poate fi definită recursiv astfel:
factorial(0)=1;
factorial(n)=n*factorial(n-1) pentru n>0;
Pentru n<0 funcția factorial nu este definită. Calcularea acestei funcții poate fi facută prin metoda următoare:
public static long factorial(int n) throws Exception {
if(n<0) throw Exception("factorial(n): n<0");
if(n==0) return 1;
return n*factorial(n-1);
}
În corpul metodei se verifică, mai întâi dacă argumentul n se încadrează în domeniul admis, iar în caz contrar se generează o excepție. Dacă argumentul este valabil, se aplică formulele de calcul recursiv al factorialului date mai sus. Recursia se încheie când se ajunge la n==0.
Atunci când o metodă invoca alta metodă (fie ea recursivă sau nu), datele metodei care invocă, inclusiv adresa instrucțiunii care urmeaza celei care a făcut invocarea, sunt puse într-o structură de memorie numita stivă, după care se transmit către metoda invocată argumentele și i se dă acesteia controlul. Stiva (engleza: stack) este o structura de memorie în care ultima dată introdusă este prima extrasă (în engleză: LIFO - Last In First Out). La revenirea din metoda invocată se obține valoarea întoarsă de aceasta și se extrag din stivă datele puse acolo înainte de invocare, continuându-se calculul.
Să urmarim acest proces în cazul invocării metodei factorial(n)
pentru n=4:
factorial(4)=4*factorial(3); se pune 4 în stivă și se invocă factorial(3);
stiva conține numărul 4;
factorial(3)=3*factorial(2); se pune 3 în stivă și se
invocă factorial(2); stiva conține numerele 3 4;
factorial(2)=2*factorial(1); se pune 2 în stivă și se
invocă factorial(1); stiva conține numerele 2 3 4;
factorial(1)=1*factorial(0); se pune 1 în stivă și se
invocă factorial(0); stiva conține numerele 1 2 3 4;
factorial(0)=1; recursia s-a incheiat, deoarece funcția nu
se mai invocă pe ea însăși. Se continuă calculul fucției factorial(1)care
a invocat-o pe factorial(0). În acest scop se scoate din stivă
1 și se calculează
factorial(1)=1*1=1; stiva conține 2 3 4.
S-a încheiat calculul lui factorial(1) și se revine în factorial(2)cu
valoarea intoarsa 1; se continuă factorial(2), extrăgând din
stivă pe 2:
factorial(2)=2*1=2; stiva conține 3 4;
factorial(3)=3*2=6; stiva conține 4;
factorial(4)=4*6=24; stiva este vidă, deci calculul
funcției recursive s-a incheiat, intorcându-se valoarea 24.
Se observa că, cu cât recursia este mai "profundă" (funcția recursivă se invocă de mai multe ori pe sine însăși), cu atât este necesară o stivă de capacitate mai mare. Daca recursia este prea "profundă", este posibil ca stiva să nu aibă capacitate suficientă. În acest caz se obține eroarea de depășire de stivă StackOverflowError (atenție: este o eroare, nu o excepție).
Calcularea factorialului se poate face și iterativ, folosind următoarea funcție, în care factorialul se calculează printr-un ciclu for:
public static long factorial(int n) throws Exception {
long fact;
if(n<0) throw new Exception("factorial(n): n<0");
fact=1;
for(int i=2; i<=n; i++) fact*=i;
return fact;
}
Ambele metode de calculare a factorialului sunt testate în aplicația din fișierul TestRecursii.java. În acest fișier se declară două clase: clasa Recursii, care conține metode statice recursive și mutual-recursive și clasa Iterații, care conține metode iterative. În același fișier există și clasa-aplicație TestRecursii, care testează metodele din celelalte două clase.
Pentru a se compara metodele din punctul de vedere al timpului de calcul, în aplicația TestRecursii s-a procedat astfel: înainte și după invocarea fiecărei metode s-a determinat timpul sistemului în milisecunde, folosind metoda System.currentTimeMillis(), apoi s-a făcut diferența. Se constata astfel că timpul de calcul al factorialului pe cale recursivă este mai mare decat pe cale iterativă.
Exemplul 2:
Un alt exemplu tipic de funcție recursivă este funcția lui Fibonacci definită astfel:
fibonacci(0)=0;
fibonacci(1)=1;
fibonacci(n)=fibonacci(n-1)+fibonacci(n-2) pentru n>1.
În fișierul TestRecursii.java sunt declarate două metode statice pentru funcția Fibonacci: una recursiva, în clasa Recursii, și alta iterativă, în clasa Iteratii. Cele două metode sunt apoi testate și comparate în clasa TestRecursii. Se poate constata că, la valori mici ale argumentului n, metoda recursivă este chiar mai rapidă decât cea iterativă. În schimb, la valori mari ale lui n, timpul de calcul al metodei recursive crește foarte rapid, devenind sensibil mai mare decât al celei iterative.
Exemplul 3:
În clasa Recursii din fisierul TestRecursii.java sunt declarate și două funcții mutual-recursive:
fct1(n,x)=2*fct2(n, 0.4*x+0.3)+x pentru n>=0
fct2(0,y)=y
fct2(n,y)=y*fct1(n-1, 1.27*y-0.89)-1 pentru n>0
Se observă că funcția fct1() invocă funcția fct2() și reciproc.