1

10. Recursivitatea

n programare, recursivitatea se refer la proprietatea unei funcii de a se putea apela pe ea nsi.

Cu alte cuvinte, spunem c o funcie este recursiv dac ea se autoapeleaz. Ea se poate autoapela fie

direct, fie indirect prin apelul altor funcii.

La apelurile recursive ale unei funcii aceasta este apelat nainte de a reveni din ea. La fiecare

reapel al funciei, parametrii i variabilele ei se aloc pe stiv ntr-o zon independent. De aceea, aceste

date au valori distincte la fiecare reapelare. Nu acelai lucru se ntmpl cu variabilele statice. Ele ocup

tot timpul aceeai zon de memorie i deci ele pstreaz valoarea la reapel.

Orice apel al unei funcii conduce la o revenire din funcia respectiv la punctul urmtor celui din

care s-a realizat apelul. Atunci cnd se revine dintr-o funcie se procedeaz la curirea stivei, adic stiva

se reface la starea ei dinaintea apelului. De aceea, orice apel al unui apel recursiv va conduce i la

curirea stivei, la o revenire din funcie, i deci parametrii i variabilele locale vor reveni la valorile lor

dinaintea reapelului respectiv. Numai variabilele statice rmn neafectate la o astfel de revenire.

Procesele recursive sunt strns legate de procesele iterative. Secvena iterativ presupune

execuia repetat a unei secvene de instruciuni, pn la ndeplinirea unei condiii (while, do-while, sau

for din C). Recursivitatea se refer la executarea repetat a unei secvene de instruciuni, ns pe parcursul

execuiei (nu la sfrit, ca n cazul iteraiei), se va verifica o condiie a crei valoare de neadevr implic

reluarea execuiei secvenei de instruciuni de la nceput, fr ca execuia curent s se fi terminat. n

momentul ndeplinirii condiiei, se va reveni n ordine invers din secvena de apeluri, relundu-se i

finalizndu-se apelurile suspendate.

Funciile recursive se utilizeaz la definirea proceselor recursive de calcul. Un proces de calcul

se spune c este recursiv, dac el are o parte care se definete prin el nsui. Un exemplu simplu de astfel

de funcie este funcia de calcul al factorialului, care se poate defini astfel:

factorial(n)=1, dac n=0, altfel

factorial(n)=n* factorial(n-1)

Alternativa:

factorial(n)=n* factorial(n-1) definete funcia factorial(n) prin ea nsi.

Un proces recursiv trebuie mereu s conin o parte care nu se definete prin el nsui. n exemplul

de mai sus, alternativa:

factorial(n)=1, dac n=0

este partea care este definit direct.

Definiia de mai sus se transmite imediat n limbajul C:

double factorial(int n)

2

{

if (n==0)

return 1.0;

else

return n*factorial(n-1);

}

S urmrim execuia acestei funcii pentru n=3. La apelul din funcia principal se construiete o

zon pe stiv n care se pstreaz adresa de revenire n funcia principal, dup apel, precum i valoarea

lui n, aa cum este prezentat n figura de mai jos:

adr1

3

rev

n

figura 1

adresa de revenire n funcia care a fcut apelul.

Deoarece n>0, se execut alternativa else. Aceasta conine expresia:

n*factorial(n-1);

care autoapeleaz (direct) funcia factorial. Reapelarea funciei se realizeaz cu valoarea n-1=3-1=2.

prin aceasta se construiete o zon nou pe stiv, care conine revenirea la evaluarea expresiei de mai

sus, precum i valoarea nou a parametrului n, adic valoarea 2. Se obine starea din figura de mai jos:

adr1

adr2

3

2

rev

n

rev

n

adresa de revenire la evaluarea expresiei n*factorial(n-1);

figura 2

La o nou reapelare a funciei factorial, n=2>0, deci din nou se execut alternativa else. Evaluarea

expresiei conduce la o reapelare cu valoarea n-1=2-1=1. Se obine urmtoarea configuraie a stivei:

3

adr1

adr2

3

2

rev

n

rev

n

rev

n

adr3

1

adresa de revenire la evaluarea expresiei n*factorial(n-1);

figura 3

Iari n=1>0 i deci se face o nou reapelare i se obine configuraia:

adr1

adr2

3

2

rev

n

rev

n

rev

n

adr2

1

adr2

0

adresa de revenire la evaluarea expresiei n*factorial(n-1); rev

n

figura 4

n acest moment n=0, deci se revine din funcie cu valoarea 1. Se cur stiva i se revine la

configuraia din figura 3. Adresa de revenire permite continuarea evalurii expresiei n*factorial(n-1). n

acest moment n are valoarea 1 i cum s-a revenit tot cu valoarea 1, se realizeaz produsul:

1*1=1

Dup evaluarea expresiei n*factorial(n-1) se realizeaz o nou revenire tot cu valoarea 1. Dup

curirea stivei se ajunge la configuraia din figura 2. n acest moment n are valoarea 2. Evalund expresia

n*factorial(n-1) se realizeaz produsul:

2*1=2

4

Apoi se revine din nou la funcia cu valoarea 2. Dup curirea stivei se ajunge la configuraia

din prima figur. n acest moment n are valoare 3. Se evalueaz expresia n*factorial(n-1) i se obine:

3*2=6

Se revine din funcie cu valoarea 6 (3!) i conform adresei de revenire, se revine n funcia

principal din care s-a apelat funcia factorial.

Programul care calculeaz factorialul unui ntreg preluat de la tastatur este prezentat n

continuare.

Ex. S se realizeze un program care calculeaz factorialul unui ntreg preluat de la tastatur.

#include

main()

{

int n;

printf("Introduceti intregul pentru care se va calcula factorialul:");

scanf ("%d",&n);

printf("fact(%d)=%d",n,factorial(n));

}

factorial(int n)

{

if(n==0)

return 1;

else

return n*factorial(n-1);

}

Referitor la funciile recursive, trebuie specificat faptul c recursivitatea constituie un nou tip de

mecanism de control al programului. Din acest motiv, fiecare funcie recursiv va avea o instruciune if

care controleaz dac funcia se va apela pe ea nsi din nou sau dac va reveni n programul apelant.

Fr o astfel de instruciune, o funcie recursiv va rula necontrolat, folosind toat memoria alocat

stivei, conducnd n final la o blocare a calculatorului.

Recursivitatea poate fi util n simplificarea anumitor algoritmi. Spre exemplu, algoritmul de

sortare Quicksort este foarte dificil de implementat dac nu se folosete recursivitatea.

5

Ex. S se realizeze un program care afieaz descresctor (sau cresctor) numerele de la n la 0 (sau

0 la n) folosind o funcie recursiv, unde n este un ntreg introdus de utilizator.

#include

main()

{

int n;

printf("Introduceti n>");

scanf("%d",&n);

afisare(n);

}

afisare(int n)

{

if (n>=0)

{

printf("%d ",n);

afisare(n-1);

}

}

Pentru afiarea numerelor n ordine cresctoare, n corpul instruciunii if se va inversa ordinea

celor dou instruciuni.

Ex: Calculul cmmdc (a,b), unde a i b sunt dou numere ntregi introduse de utilizator.

a=28, b=12

1. Metoda restului:

a=b

b=a%b

dac b=0 cmmdc=a

a = 28 12 4

b = 12 4 0

dac b=0 afieaz cmmdc=a altfel

calculeaz cmmdc (b, a%b)

2. Metoda scderilor succesive:

dac a=b cmmdc = a dac a>b se calculeaz cmmdc (a-b,b) dac b>a se calculeaz cmmdc (a,b-a)

6

a = 28 16 (28 - 12) 4 (16 - 12) 4 4

b = 12 12 12 8 (12 - 4) 4 (8 - 4)

dac a=b afieaz cmmdc=a altfel

dac a>b calculeaz cmmdc (a-b, b) altfel

calculeaz cmmdc (a, b-a)