Download - SD - Breaviar_Lab_1.pdf
-
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.