Exista o stransa legatura intre recursivitate si rationamentul inductiv.
Amintim ca, in acest rationament, se stabileste ca o anumita proprietate
P este valabila pentru toate elementele unui sir de entitati E1,
E2, E3, ... Ek, Ek+1, ....
Rationamentul contine doua etape:
|
In programarea orientata pe obiecte, functiile si procedurile se realizeaza
sub forma de metode. In consecinta, functiile si procedurile recursive
sunt metode recursive.
Exemple de functii recursive:
1. Functia factorial:
2. Functia lui Fibonacci:
3. Functia lui Ackerman
|
Din exemplele de mai sus, constatam urmatoarele:
Procedurile nu au valoare intoarsa, ci numai efect lateral. In consecinta, folosirea procedurilor recursive se bazeaza pe cumularea efectelor laterale, care consta in modificarea valorilor unor variabile globale sau valorilor parametrilor procedurii. In limbajul Java nu exista variabile globale, dar pot fi modificate valorile unor campuri ale clasei careia ii apartine metoda recursiva sau ale unor componente ale obiectelor primite ca parametri. |
De foarte multe ori, trecerea de la varianta recursiva la cea iterativa
a algoritmului se face inlocuind functia recursiva printr-un ciclu. De
exemplu, pentru calcularea factorialului, se poate folosi fie functia recursiva
static long factorial(long n) throws Exception
{
fie varianta iterativa static long fact(long n) throws Exception {
Complexitatea ambelor functii este liniara O(n). Vom arata totusi, ca exista si situatii in care inlocuirea recursiei prin iteratie necesita folosirea unei structuri de stiva. |
Exemplu
In fisierul Fibonacci.java se da un exemplu de aplicatie in care se testeaza doua variante de calcul al functiei Fibonacci: varianta recursiva, care respecta definitia data mai sus, si varianta iterativa. Argumentul functiei se da ca argument in linia de comanda. Pentru fiecare din aceste variante se determina si timpul de calcul (in milisecunde). In acest scop, inainte si dupa invocarea metodei respective se invoca metoda System.currentTimeMillis(), care intoarce timpul indicat de ceasul sistemului, si se face diferenta, obtinand timpul de calcul in milisecunde. Este posibil ca, pentru valori mici ale argumentului functiei, durata de calcul in ambele variante sa fie 0 (adica mai mica de o milisecunda). Se consta insa ca la valori mai mari ale argumentului (peste 25) diferenta dintre cele doua variante devine din ce in ce mai mare, in defavoarea celei recursive. Memoria ocupata este, de asemenea, mult mai mare la varianta recursiva, unde se pun pe stiva sistemului toate datele de la invocarile intermediare ale functiei, in timp ce in varianta iterativa este necesar sa se memoreze de la o iteratie la alta numai doua valori: f1=fib(i-1) si f2=fib(i-2). Explicatia este ca cei doi algoritmi folositi pentru calculul functiei Fibonacci au complexitati diferite. In varianta iterativa exista un singur ciclu, care se parcurge de n-2 ori, deci algoritmul are complexitate liniara O(n). In varianta recursiva, numarul de apeluri recursive ale functiei fibonacci(k) se obtine ca suma unei progresii geometrice cu ratia 2 si deci este de ordinul 2n. Intr-adevar, pentru calcularea lui fibonacci(n) este necesar sa se calculeze fibonacci(n-1) si fibonacci(n-2). Pentru calcularea fiecareia din aceste valori sint necesare alte doua apeluri ale functiei fibonacci si asa mai departe, pana se ajunge la fibonacci(1). Complexitatea algoritmului recursiv este deci, in acest caz, exponentiala O(2n). |