Există o strânsa legătură între recursivitate și
raționamentul inductiv. Amintim că, în acest raționament, se stabilește
că o anumită proprietate P este valabilă pentru toate elementele unui
șir de entități E1, E2, E3, ... Ek,
Ek+1, ....
Raționamentul conține doua etape:
|
În programarea orientată pe obiecte, funcțiile și procedurile se
realizează sub formă de metode. În consecință, funcțiile și procedurile
recursive sunt metode recursive.
Exemple de funcții recursive:
1. Funcția factorial: 2. Funcția lui Fibonacci: 3. Funcția lui Ackerman |
Din exemplele de mai sus, constatăm urmatoarele:
Procedurile nu au valoare întoarsă, ci numai efect lateral. În consecință, folosirea procedurilor recursive se bazează pe cumularea efectelor laterale, care constă în modificarea valorilor unor variabile globale sau valorilor parametrilor procedurii. În limbajul Java nu există variabile globale, dar pot fi modificate valorile unor câmpuri ale clasei căreia îi aparține metoda recursivă sau ale unor componente ale obiectelor primite ca parametri. |
De foarte multe ori, trecerea de la varianta recursivă la cea
iterativă a algoritmului se face înlocuind funcția recursivă printr-un
ciclu. De exemplu, pentru calcularea factorialului, se poate folosi fie
funcția recursivă
static long factorial(long n) throws Exception { fie varianta iterativă static long fact(long n) throws Exception { Complexitatea ambelor funcții este liniară O(n). Vom arăta totuși, că există și situații în care înlocuirea recursiei prin iterație necesită folosirea unei structuri de stivă. |
Exemplu În fisierul Fibonacci.java se dă un exemplu de aplicație în care se testează doua variante de calcul al funcției Fibonacci: varianta recursivă, care respectă definiția dată mai sus, și varianta iterativă. Argumentul funcției se dă ca argument în linia de comandă. Pentru fiecare din aceste variante se determină și timpul de calcul (în milisecunde). În acest scop, înainte și după invocarea metodei respective se invocă metoda System.currentTimeMillis(), care intoarce timpul indicat de ceasul sistemului, și se face diferența, obținând timpul de calcul în milisecunde. Este posibil ca, pentru valori mici ale argumentului funcției, durata de calcul în ambele variante să fie 0 (adică mai mică de o milisecundă). Se constată însă că la valori mai mari ale argumentului (peste 25) diferența dintre cele doua variante devine din ce în ce mai mare, în defavoarea celei recursive. Memoria ocupată este, de asemenea, mult mai mare la varianta recursivă, unde se pun pe stiva sistemului toate datele de la invocările intermediare ale funcției, în timp ce în varianta iterativă este necesar să se memoreze de la o iterație la alta numai doua valori: f1=fib(i-1) și f2=fib(i-2). Explicația este că cei doi algoritmi folosiți pentru calculul funcției Fibonacci au complexități diferite. În varianta iterativă există un singur ciclu, care se parcurge de n-2 ori, deci algoritmul are complexitate liniară O(n). În varianta recursivă, numarul de apeluri recursive ale funcției fibonacci(k) se obține ca suma unei progresii geometrice cu rația 2 și deci este de ordinul 2n. Într-adevar, pentru calcularea lui fibonacci(n) este necesar sa se calculeze fibonacci(n-1) si fibonacci(n-2). Pentru calcularea fiecăreia din aceste valori sunt necesare alte două apeluri ale funcției fibonacci și așa mai departe, până se ajunge la fibonacci(1). Complexitatea algoritmului recursiv este deci, în acest caz, exponentială O(2n). |