7/25/2019 SD - Breaviar_Lab_1.pdf

1/2

Structuri de date Laborator 1

Recursivitate I

Breviar teoretic

Funciile recursive sunt acelea care prezint proprietatea c se apeleaz pe ele nsele.Pentru a nu face un

ciclu infinit, este obligatoriu ca funcia s aib un anumit caz (caz de baz) care s determine returnarea

unei valori prestabilite i care deci s determine terminarea apelurilor recursive.

Exemplu: (Funcie care afieazsemnul * de n ori iar la final afieaz newline)

1. void print (int n) {

2. if ( n == 0 )

3. printf (\n); //cazul de baz4. else {

5. printf (*);

6. print (n-1); //apelul recursiv; se observ c fr cazul de bazprogramul ar fi intrat la

7. } //infinit pe aceast ramur i ar fi fcut print(n-1) ntr-una

8. }

n exemplul anterior funcia afieaz semnul* i apoi se realizeaz apelul recursiv. Dac am fi schimbat

ntre ele liniile 5 i 6 lucrurile ar fi stat diferit. Programul ar fi realizat apelul recursiv prima oar, deci nu ar

fi ajuns la printarea semnului * dect dup ce a terminat de executat print(n-1). Pentru a putea face acest

lucru, programul salveaz automat pe stiv setul de instruciuni rmase dup apelul recursivi l va scoatede acolo doar atunci cnd firul de execuie se va ntoarce la funcia care adeterminat ncrcarea n stiv a

acelor instruciuni. Practic, n acest situaie, afirile vor ncepe s aib loc n ordine invers, dupa ce

programul a ajuns la cazul de baz.

OBSERVATIE: Schimbarea liniei 5 cu linia 6 va determina o modificare a ceea ce se va afia. Programul va

afia mai nti newline i abia apoi va afia de n ori semnul *.

Exemplu: (Apelm din main print(5). Imaginile de mai jos reprezint stiva de memorie)

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

* *

print(4) print(0) print(4)print(5)

Observai c stiva se

ncarc pn se ajunge lacazul de baz, dup care

se golete. Ultima *

ncrcat e prima care

iese si este afiat.

7/25/2019 SD - Breaviar_Lab_1.pdf

2/2

Prin funcii mutual recursive nelegem cel puin dou funcii care se apeleaz una pe cealalt. Ambele se

vor comporta ca nite funcii recursive, deci, pentru a v asigura ca nu se produce un ciclu infinit, punei

caz de baz ambelor funcii.

Exemplu: (GREIT)

void A (int n) {

printf(%c, A);

if (n != 0 ) B(n-1); //caz de baz

}

void B (int n) {

printf((%c, B);

A(n-1); //nu are caz de baz

}

Motivul pentru care exemplul este greit este faptul c funcia B nu are caz de baz i exist anumite situaii

n care va intra n bucl infinit. Dac n main facem apelul A(3), programul nu va avea condiie de oprire.

Asta pentru c n devine 0 atunci cnd este n funcia B. Cum aceasta nu verific valoarea lui n, ea apeleaz

din nou funcia A, care l va primi pe n=-1 != 0.