Subprograme recursive.

Prof. Cojocaru Liuba

Recapitulare: de la subprogram obișnuit la
subprogram recursiv
Subprogramul este un bloc de instrucțiuni care realizează o sarcină.
Subprogram recursiv = subprogram care se apelează pe sine:
❑ direct;
❑ sau indirect, prin alt subprogram.
Ideea centrală a recursiei:
o problemă se rezolvă reducând-o la aceeași problemă, dar într-o
formă mai simplă.
 Definiția recursiei
Recursia este tehnica de rezolvare a unei probleme prin reducerea ei
la una sau mai multe probleme mai mici, de același tip.
Un subprogram recursiv conține:
❑ caz de bază – situația în care răspunsul se obține direct;
❑ caz general – situația în care subprogramul se autoapelează;
❑ pas de reducere – fiecare apel trebuie să apropie problema de
cazul de bază.
Reținut: fără caz de bază corect, recursia nu se oprește.
Structura generală a unui subprogram recursiv
tip nume(parametri)
{
if (caz_baza)
return rezultat_direct;
else
return expresie_cu_nume(problema_mai_mica);
}

Observații:
o apelul recursiv nu este întâmplător;
o parametrii trebuie modificați astfel încât problema să devină mai mică;
o fiecare apel nou lucrează cu propriile valori.
 Cum funcționează recursia în memorie?

La fiecare apel recursiv:

o se creează un nou cadru în stiva de apeluri;
o se memorează parametrii și variabilele locale;
o execuția coboară până la cazul de bază;
o apoi rezultatele se întorc invers, de jos în sus.
Idee-cheie:
recursia nu înseamnă „magie”; înseamnă o succesiune de apeluri stocate
în stivă.
 Exemplul clasic: factorial
Definiție matematică:
o 0! = 1
o n! = n * (n-1)!, pentru n > 0
Implementare C++:
long long fact(int n) Identificare:
{ o caz de bază: n == 0 sau n == 1
if (n == 0 || n == 1) o caz general: n * fact(n - 1)
return 1;
return 1LL * n * fact(n - 1);
}
 Urmărirea execuției: fact(4)

fact(4) = 4 * fact(3)
fact(3) = 3 * fact(2)
fact(2) = 2 * fact(1)
fact(1) = 1

Revenirea:
❑ fact(2) = 2 * 1 = 2
❑ fact(3) = 3 * 2 = 6
❑ fact(4) = 4 * 6 = 24
Concluzie:
apelurile coboară până la cazul de bază, apoi rezultatul se reconstruiește la întoarcere.
 Când utilizăm recursia
Recursia este potrivită când problema:
o are o structură repetitivă;
o se poate descompune natural în subprobleme similare;
o are un caz simplu de oprire.

Exemple potrivite:
•factorial; putere; CMMDC; suma cifrelor; numărul de cifre; conversii de baze;
prelucrarea recursivă a tablourilor; parcurgerea structurilor ierarhice.
Subprogram recursiv cu doi parametri: CMMDC
Idee:
cmmdc(a, b) = cmmdc(b, a % b), până când b == 0
int cmmdc(int a, int b)
{ Exemplu:
if (b == 0) cmmdc(24, 18)
return a; → cmmdc(18, 6)
return cmmdc(b, a % b); → cmmdc(6, 0)
} →6

Avantaj: exemplu scurt, clar și foarte potrivit pentru doi parametri.

Subprogram recursiv cu doi parametri pe tablou
Problema: suma elementelor unui tablou:
int suma(int a[], int n)
{
if (n == 0)
return 0;
return suma(a, n - 1) + a[n - 1];
}
Interpretare: Aplicații didactice:
o suma primelor n elemente o suma notelor;
o se reduce la suma primelor n-1 o numărul valorilor pare;
elemente + ultimul element o căutarea unui maxim/minim.
 Recursie directă și recursie indirectă
Recursie directă:
subprogramul se apelează pe sine direct.

Ex.: fact(n) apelează fact(n - 1)

Recursie indirectă:
subprogramul A apelează B, iar B ajunge să apeleze A.
Exemplu conceptual:
o estePar(n) apelează esteImpar(n - 1)
o esteImpar(n) apelează estePar(n - 1)
 Exemplu de recursie indirectă
bool estePar(int n)
{
if (n == 0) return true;
return esteImpar(n - 1);
Observații:
}
❑ există două subprograme;
❑ apelurile alternează;
bool esteImpar(int n)
❑ și aici sunt obligatorii cazurile de bază.
{
if (n == 0) return false;
return estePar(n - 1);
}

Concluzie:
recursia indirectă este mai greu de urmărit și cere mai multă atenție
 Apelarea subprogramelor recursive
Un subprogram recursiv se apelează ca orice alt subprogram:
o din main();
int main()
o din alt subprogram;
{
o sau din el însuși. cout << fact(5);
return 0;
}
Reguli importante la apel:
o datele inițiale trebuie să fie valide;
o trebuie cunoscut domeniul admis al parametrilor;
o trebuie evitate valorile care nu duc spre cazul de bază.
 Greșeli frecvente în recursie

o lipsește cazul de bază; Exemplu periculos:

o cazul de bază există, dar nu poate fi atins;
return f(n);
o parametrii nu se modifică corect;
o problema nu se micșorează;
o se repetă inutil aceeași muncă;
o se apelează funcția pe date invalide.
 Supraîncărcarea stivei: cauze
Supraîncărcarea stivei apare când sunt prea multe apeluri recursive sau
recursia nu se oprește.

Cauze frecvente:
o recursie infinită;
o lipsa cazului de bază;
o reducere prea lentă a problemei;
o apeluri foarte adânci;
o variabile locale mari la fiecare apel.
Efect:
programul se oprește anormal.
Cum evităm supraîncărcarea stivei
o definim corect cazul de bază;
o verificăm dacă fiecare apel apropie problema de oprire;
o validăm datele de intrare;
o testăm întâi pe valori mici;
o evităm recursia pentru probleme cu adâncime foarte mare;
o alegem iterația dacă soluția iterativă este mai simplă și mai sigură;
o evităm recalculările inutile.
Exemplu:
Fibonacci recursiv naiv este elegant, dar ineficient.
 Recursie sau iterație?
Recursia
o cod mai scurt și mai expresiv;
o potrivită pentru probleme definite natural recursiv;
o ușor de formulat pentru structuri ierarhice.
Iterația
o consumă mai puțină memorie;
o de multe ori este mai rapidă;
o este mai sigură pentru repetări foarte mari.
Concluzie:
nu alegem recursia „pentru că este frumoasă”, ci pentru că este potrivită problemei.
Pași pentru proiectarea unui algoritm recursiv
1) Înțelege problema.
2) Identifică forma mai mică a aceleiași probleme.
3) Stabilește cazul de bază.
4) Scrie relația de recurență.
5) Verifică dacă există progres.
6) Testează pe exemple mici.
7) Abia apoi implementează în C++.
Întrebare de control:
„Apelul recursiv chiar micșorează problema?”
Algoritm recursiv util în procesul de studiu
Problema: să calculăm suma notelor unei grupe
int sumaNote(int note[], int n)
{
if (n == 0)
return 0;
return sumaNote(note, n - 1) + note[n - 1];
}
Extindere:
o media = 1.0 * sumaNote(note, n) / n
o numărul notelor peste 8;
o numărul notelor pare/impare;
o maximul într-un tablou.
 Concluzii

De reținut:
o un subprogram recursiv se apelează pe sine;
o orice recursie corectă are caz de bază și progres;
o fiecare apel folosește stiva de apeluri;
o recursia poate fi directă sau indirectă;
o nu orice problemă trebuie rezolvată recursiv;
o o recursie bună este corectă, clară și sigură.
MULȚUMESC!