RECURSIVITATE

Recursivitatea este un mecanism general de elaborare a algoritmilor. O funcţie se numeşte recursivă dacă ea se autoapelează, fie direct (în definiţia ei se face apel la ea însăşi), fie indirect (funcţia X apelează funcţia Y, care apelează funcţia X). Recursivitatea a apărut din necesitati practice, date de transcrierea directă a formulelor matematice recursive. Apoi, acest mecanism a fost extins, fiind utilizat în elaborarea multor algoritmi.

De exemplu, definiţia recursivă a lui n! (factorialul lui n) este :

Functia recursivă se va scrie astfel:

factorial

Se observă ca funcţia factorial se autoapelează. Autoapelul se realizează prin instrucţiunea return factorial(n-1)*n.
Recursivitatea utilizează segmentul de stivă pentru a memora datele programului apelant, câtă vreme calculatorul rulează programul apelat. De fiecare dată când o funcţie se autoapelează, se creează un nou nivel în segmentul de stivă.

Funcţionarea poate fi urmărită în figura de mai jos:

principiuRecursivitate

Fiecare apel de funcţie lucrează cu datele aflate pe nivelul corespunzator acelui apel. La ieşirea din apelul unei funcţii, nivelul respectiv se eliberează şi datele aflate acolo se pierd. Există posibilitatea ca subprogramul să lucreze direct cu variabilele globale, dar în acest caz, subprogramul işi pierde independenţa.

Observaţii :

-       în cazul unui număr mare de autoapelări, există posibilitatea ca segmentul de stivă sa se ocupe total, caz în care programul se va termina cu eroarea STACK OVERFLOW. Aceasta se întamplă mai ales atunci când condiţia de terminare este pusă greşit şi subprogramul se apelează la nesfârşit.
-      pentru orice algoritm recursiv există unul iterativ, care rezolvă aceeaşi problemă.
-     mecanismul recursivităţii înlocuieste instrucţiunile repetitive.
-     datorită faptului că la fiecare autoapel se ocupă o zonă de memorie, recursivitatea este eficientă numai dacă numărul de autoapelări nu este prea mare, pentru a nu se ajunge la umplerea zonei de memorie alocată.
-        recursivitatea oferă avantajul unor soluţii mai clare pentru probleme şi a unei lungimi mai mici a programului. Ea prezintă însă dezavantajul unui timp mai mare de execuţie şi a unui spaţiu de memorie alocată mai mare. Este de preferat ca, atunci când programul recursiv poate fi transformat cu uşurinţă într-unul iterativ, să se facă apel la cel din urmă.

Este clar că ordinea executării instructiunilor va depinde de locul în care se întâlneşte apelul recursiv. Să studiem trei cazuri:

Situaţia 1

Pentru structura generică:

                        tip_func_rec sub (listă de parametri){
                                    {setul “a“de instrucţiuni;}
                                    if(condiţie) sub (parametri); // apelul recursiv
                        }

se va executa setul “a“ de instrucţiuni, în ordine “directă” (prima dată cele întâlnite la primul apel al funcţiei recursive sub, ultima dată celor întâlnite la ultimul apel al funcţiei recursive sub).

De exemplu, pentru programul de mai jos:

recurs_s1

şi n=3, m=7, se vor obţine rezultatele:

rezultatRecurs_s1

O variantă on-line poate fi experimentată la sau la recurs_s1

si asa mai departe

Up Home Structura Site

Situaţia 2:

Pentru structura generică:

                        tip_func_rec sub (listă de parametri){
                                    if(condiţie) sub (parametri); // apelul recursiv
                                    {setul “b“de instrucţiuni;}
                        }

se va executa setul “b“ de instrucţiuni, în ordine “inversă” (prima dată cele întâlnite la ultimulul apel al funcţiei recursive sub, ultima dată celor întâlnite la primul apel al funcţiei recursive sub).

De exemplu, pentru programul de mai jos:

recurs_s2

şi n=3, m=7, se vor obţine rezultatele:

rezultatRecurs_s2

O variantă on-line poate fi experimentată la sau la recurs_s2

Up Home Structura Site

Situaţia 3 (combinaţie a celor două anterioare):

fie structura generică:

                        tip_func_rec sub (listă de parametri){
                                    {setul “a“de instrucţiuni;}
                                    if(condiţie) sub (parametri); // apelul recursiv
                                    {setul “b“de instrucţiuni;}
                        }

De exemplu, pentru programul de mai jos:

recurs_s3

şi n=3, m=7, se vor obţine rezultatele:

rezultRecurs_s3

O variantă on-line poate fi experimentată la sau la recurs_s3

Up Home Structura Site

Un exemplu practic pentru această din urmă situaţie se prezintă în programul următor, care afişează în ordine inversă valorile citite de la tastatură (introducerea datelor se consideră încheiată când se introduce valoarea zero)

recurs_s4