Laborator Informatica

Laborator 8. Clasa a XI-a C Recursivitate

Prin recursivitate se înţelege faptul că o funcţie se apelează pe ea însăşi (apelul apare când funcţia este încă în execuţie). Se folosesc algoritmi recursivi de obicei atunci când calculele efectuate pot fi descrise în formă recurentă (de exemplu: n!=n*(n-1)! sau xn=x*xn-1, adică rezultatul de la etapa curentă se poate exprima în funcţie de rezultatul obţinut la etapa precedentă). O funcţie recursivă scrisă corect trebuie să respecte regulile: 1. funcţia trebuie să se execute, cel puţin într-o situaţie, fără să se autoapeleze; această situaţie se numeşte condiţie de oprire. 2. funcţia recursivă se va autoapela într-un mod în care se tinde spre atingerea situaţiei de execuţie fără autoapel. Pentru a permite apelarea recursivă a funcţiilor, limbajul C++ foloseşte o stivă internă. La fiecare apel recursiv se salvează în stivă starea curentă a execuţiei funcţiei (adresa de revenire în funcţia care a făcut apelul, variabilele locale ale funcţiei apelate recursiv, parametrii funcţiei transmişi prin valoare). Din cauza faptului că la fiecare autoapel se ocupă o zonă de stivă, recursivitatea este eficientă numai dacă numărul de autoapeluri nu este mare, astfel încât să nu se ajungă în situaţia umplerii stivei. 

Vezi Laborator8/mecanismul_recursivitatii

Recursivitatea oferă avantajul unor soluţii mai clare pentru probleme. Ea prezintă însă dezavantajul unui timp mai mare de execuţie şi al unui spaţiu ocupat în memorie mai mare. Exemple: 1. Calculul sumei cifrelor unui număr natural n. nerecursiv int n; int suma_cifre(int x) {int s=0; while(x!=0) {s=s+x%10; x=x/10;} return s;} void main() {cin>>n; cout<<suma_cifre(n);}

recursiv

int n; int suma_cifre(int x) {if (x==0) return 0; // condiţia de oprire //suma cifrelor numărului 0 se cunoaşte; nu mai este nevoie de alt autoapel else return x%10+suma_cifre(x/10); // autoapel /*- relaţia recurentă de calcul se bazează pe faptul că suma cifrelor unui număr este egală cu ultima cifră a numărului, adunată la suma cifrelor numărului dat, fără ultima sa cifră - suma cifrelor numărului x fără ultima sa cifră se calculează reapelând recursiv funcţia cu parametrul x/10 - funcţia se va autoapela până când condiţia de oprire devine adevărată */ } void main() {cin>>n; cout<<suma_cifre(n);} //suma_cifre(123)=3+suma_cifre(12)=3+2+suma_cifre(1)=3+2+1+suma_cifre(0)=3+2+1+0=6

Laborator 8. Clasa a XI-a C Recursivitate 2. Calculul ab, cu a şi b numere naturale. nerecursiv int a,b; int putere(int b,int e) {int i,p=1; for(i=1;i<=e;i++) p=p*b; return p;} void main() {cin>>a>>b; cout<
recursiv

int a,b; int putere(int baza,int exponent) {if (exponent==0) return 1; // condiţia de oprire //valoarea baza0 se cunoaşte; nu mai este nevoie de alt autoapel else return baza*putere(baza,exponent-1); //autoapel /* relaţia de recurenţă este be=b*be-1; be-1 se calculează reapelând recursiv funcţia putere, cu parametrul corespunzător exponentului micşorat cu o unitate; funcţia se va autoapela până când condiţia de oprire devine adevărată */ } void main() {cin>>a>>b; cout<
3. Calculul n!, cu n număr natural. nerecursiv int n; int fact(int x) {int i,p=1; for(i=1;i<=x;i++) p=p*i; return p;} void main() {cin>>n; cout<
recursiv

int n; int fact(int x) {if (x==0) return 1; // condiţia de oprire //valoarea 0! se cunoaşte; nu mai este nevoie de alt autoapel else return x*fact(x-1); // autoapel /* relaţia de recurenţă este x!=x*(x-1)! (x-1)! se calculează reapelând recursiv funcţia fact, cu parametrul micşorat cu o unitate; funcţia se va autoapela până când condiţia de oprire devine adevărată */ } void main() {cin>>n; cout<
Vezi Laborator8/exemple_de_algoritmi Exerciţii: I. 1.

Laborator 8. Clasa a XI-a C Recursivitate 2.

3.

II. 1. Scrieţi o funcţie recursivă care să calculeze suma primelor n numere naturale. Folosiţi relaţiile de recurenţă din Laborator8/exemple_de_algoritmi. Exemplu: n=5 S=15 2. Scrieţi o funcţie recursivă care să calculeze cmmdc a două numere naturale. Folosiţi relaţiile de recurenţă din Laborator8/exemple_de_algoritmi. Exemplu: n=10 m=4 cmmdc=2 3. Pentru o valoare n citită de la tastatură, să se afişeze recursiv triunghiurile: #include 1 void afis(int nr_crt, int cate_nr_sunt_pe_linie) 12 {if (nr_crt <= cate_nr_sunt_pe_linie) 123 { cout<>n; for(int i=1;i<=n;i++) { afis(1,i); // afişează linia cu numărul de ordine i cout<<endl;} }

1 2 3....n ..... 123 12 1 4. Să se calculeze recursiv suma cifrelor pare existente în scrierea unui număr natural n. (vezi exemplul 1) Exemplu: n=1245 S=6 5. Se dau doi vectori x şi y, cu n numere naturale în fiecare. Să se calculeze S=x[1]y[1]+x[2]y[2]+ …+ +x[n]y[n]. Se va utiliza o funcţie recursivă care calculează ab. (vezi exemplul 2) Exemplu: n=3 x=(1, 3, 4) y=(5, 2, 2) S=15+32+42=26 6. Se dă un şir de n numere naturale. Să se scrie o funcţie recursivă care determină de câte ori apare o valoare x în şirul dat. (vezi exemplul de mai jos) Exemplu: n=5 V=(1,2,3,2,1) x=2 2 apariţii

Laborator 8. Clasa a XI-a C Recursivitate

Nerecursiv

Recursiv

int aparitii() {int ap=0; for(int i=1 ;i<=n ;i++) if (v[i]==x) ap++; return ap; }

int aparitii(int i)

/*recursivitatea va lua locul instrucţiunii for; din acest motiv contorul din for apare ca parametru pentru funcţia recursivă; parametrul va indica la ce element din vector s-a ajuns cu parcurgerea */ { if (i>n) return 0; //s-a terminat vectorul de parcurs else if (v[i]==x) return 1+aparitii(i+1); else return aparitii(i+1); }

/* dacă elementul curent este egal cu cel căutat, numărul de aparţii creşte cu o unitate şi prin autoapelare se trece la elementul următor din vector; dacă elementul curent este diferit de cel căutat doar se trece mai departe în vector, autoapelând funcţia; În funcţiile recursive nu se fac iniţializări în mod explicit pentru variabile care calculează sume, produse etc; Fiind recursivă, funcţia se va executa identic la fiecare iteraţie şi atunci variabila se va reiniţializa la fiecare autoapelare, lucru nedorit. */ //în main se va apela cu aparitii(1)

7. Se citeşte un număr natural n. Să se determine dacă numărul este egal cu suma factorialelor cifrelor lui. Se va scrie o funcţie recursivă care calculează factorialul unui număr natural. (vezi exemplul 3) Exemplu: n=145 DA (145=1!+4!+5!) n=146 NU 8. Se dă un şir de n numere naturale. Să se determine recursiv câte din numerele din şir sunt prime cu o valoare x dată. Se va scrie şi o funcţie recursivă care calculează cmmdc a două numere. (vezi exerciţiul 2) Exemplu: n=5 V=(10,20,3,25,12) x=4 2 9. Se dă un şir de n numere naturale. Să se determine recursiv suma numerelor pătrate perfecte din şir. Exemplu: n=5 V=(10,20,4,25,12) 29 10. Să se verifice, folosind o funcţie recursivă dacă un şir de n numere întregi conţine numai numere negative. Exemplu: n=5 V=(-1,-2,-3,-2,-1) DA V=(-1,2,-3,2,-2) NU