04/12/231

Tehnici de programareTehnici de programare

1.Recursivitate

04/12/232

Structura semastrului II:

-14 saptamani

-1 saptamana vacanta de pasti (dupa)

-4 saptamani sesiunea iunie-iulie

Structura disciplinei:

- 2 ore curs/saptamana

-2 ore/saptamana laborator/subgrupa- obligatoriu

-1 ora proiect/grupa saptamanal

OBS. Lucrarile de laborator se recupereaza la anul in sem II

Calculul notei la examen

NF=0.1*TC+0.1*Test+ 0.7*NEX+1of

TC,Test,NEX>=5

Se poate da ex. partial

04/12/233

  

Bibliografie   1.Waite M., Prata St., Martin D. ,”C Primer Plus”, Howard W. Sans & C0, 1986

2.Jamsa K., Klander L.- Totul despre C si C++. Manual fundamental de programare in C si C++. Teora 20023.Schildt H. – C manual complet. Teora 19984. Schildt H. – C++ manual complet. Teora 19985.Kernighan B., Ritchie D. – The C Programming Language, Printice Hall,19886.Cristea V., Kalisz E., Giumale C., Panoiu F.- Limbajul C standard, Teora 19927.Marian Gh., si alti- Modele de grile pentru examenele de diploma si absolvire, Editura Universitaria 2004 ISBN 973-8043-503-38.Patrascoiu O., Marian Gh., Mitroi N. – Elemente de grafuri si combinarorica. Metode, algoritmi si programe, Editura ALL 1993 ISBN 973-571-017-X9. Patrascoiu O., Mitroi N. , Marian Gh.- Limbajul C, Teorie si programe, Editura Microcomputer Service, Craiova, 1994.10.Petrovici V., Goicea F. – Programare in limbajul C, Ed. Tehnica 198811.Marian Gh., Badica C., Lascu M.,Iordache S.-Limbajul C-Aplicatii, Editura Spirit Romanesc, Craiova 199712.Mocanu M., Marian Gh., Badica I., C., Badica P., C. - 333 probleme de programare, Editura TEORA, Bucuresti, 1993.

 

04/12/234

Introduction Introduction

DefintiiNotiunea de recursivitate din programare este derivata in mod natural din notiunea de recusivitate din matematica, unde o notiune este definita recursiv daca in cadrul definitiei sale apare insasi notiunea ce se defineste.

Exemple:-factorial

1 daca n=0n!= n *(n-1)! daca n>0

04/12/235

-sirul fibonacci

f(0)=0,

f(1)=1,

f(i)=f(i-1)+f(i-2) pentru i>1.

-cel mai mic divizor comun

a daca a=b

cmmdca,b)=

cmmdc(b,a mod b)daca a<> b

Etc.

04/12/236

In programare, instrumentul necesar si suficient pentru a exprima programe recursive este subprogramul pentru ca subprogramul da un nume unei actiuni care poate fi invocata prin numele respectiv.

Recursivitatea poate fi directa atunci cand in corpul subprogramului apare apelul acelui subprogram, sau indirecta daca apelul apare in corpul altui subprogram care se apleleaza din primul subprogram.

Autoapelul provoaca o noua activare a aceluiasi subprogram, ceea ce presupune executia instructiunilor subprogramului, incepand cu prima instructiune a acestuia si pana la autoapel, cand se activeaza din nou subprogramul s.a.m.d. Ca atare, partea de inceput a subprogramului se poate executa de o infinitate de ori. Pentru a se evita o asemenea situatie trebuie ca autoapelul subprogramului sa fie conditionat de indeplinirea unei anumite conditii. Daca conditia de autoapel (C) este indeplinita, atunci subprogramul este reactivat (reapelat), in caz contrar sirul de activari (apeluluri) ale subprogramului se intrerupe si se executa secventele ramase de executat din subprogram, activate in ordine inversa activarii.

04/12/237

C=adevarat C=adevarat C=adevarat

Subprogram S

Subprogram S

Subprogram S

Subprogram S

daca Catunci S

daca Catunci S

daca Catunci S

daca Catunci S

(2) (3) (4)

(5) (6)

apel S apel S apel S C=fals

(15) (16) (14)

(13) (12) (11)

(10)

(7) (8)apel subprogram

 S (1)

Revenire in Programul

apelant (17)

(9)

04/12/238

Figura 1.2.

  C=adevarat  

SubprogramS

Subprogram S1

Subprogram S

Subprogram S1

daca Catunci S

daca Catunci S

(2) (3) (4) (5)

(6)

apel S1 apel S apel S1 C=fals

(15) (16) (14)

(13) (12) (11) (10)

(7) (8)

(9)

apel subprogram S

revenire in programul

apelant

(1)

(17)

S1 S1

In figura 1.2 se prezinta schematic executia unui subprogram indirect recursiv S, subprogram ce este reapelat prin intermediul subprogramului S1.

04/12/239

Apelul unui subprogram recursiv, ca si al unuia nerecursiv presupune alocarea de memorie pe stiva a variabilelor locale, a parametrilor si a adresei de revenire. Ca atare pentru a nu se ajunge in situatia depasirii stivei se recomanda utilizarea unei solutii recursive numai daca numarul autoapelului (adancimea recursivitatii) nu este mare.

In cazul utilizarii recursivitatii se mai recomanda utilizarea variabilelor globale pentru a se evita crearea unor dubluri de variabile pe stiva.

Avantajul recursivitatii este acela ca:- reduce lungimea textului sursa;- conduce la solutii clare in comparatie cu solutiile iterative.

Recursivitatea se recomanda:- in problemele ale caror solutii pot fi definite in termeni recursivi;- in cazul problemelor complexe rezolvate prin backtracking.Intotdeauna o problema recursiva are si o rezolvare iterativa si invers.Utilizarea tehnicilor recursive nu conduce intotdeauna la solutii optime. Ca

atare, se recomanda o analiza a eficientei solutiei recursive si a celei nerecursive si alegerea solutiei celei mai avantajoase

04/12/2310

Exemplul 1: Sa se calculeze n! intr‑o varianta iterativa si alta recursiva. Se stie ca :

1

daca n=0n!= n.(n-1)! daca n>0 Pseudocodul pentru varianta iterativa si cea recursiva:functia FACT1(i) este:

{iterativ}

f:=1; pentru i=1,n,1 repeta │

f=f*i └ FACT1:=fsfarsitfunctia FACT2(i) este:

{recursiv} daca i>0 atunci │

FACT2=i*FACT2(i‑1) │ altfel | FACT2=1 └Sfarsitciteste npentru k=1,n,1 repeta │

f1=FACT1(k);│ f2:=FACT2(k);│ scrie f1,f2└stop

 

04/12/2311

Programul C:#include <stdio.h>/* functia recursiva*/int factr(int i){

if (i>0) return i*factr(i-1)

else return 1;}/* functia iterativa*/int facti(int i{int p,k;p=1;for (k=1; k<i; k++) p=p*k;return p;}void main(){

printf(“ Factr( %d)=%d\n Facti(%d)=%d\n”, 5,factr(5),5,facti(5)}

04/12/2312

Exemplul 2: Sa se genereze un sir de cifre reprezentand scrierea rasturnata a unui numar intreg si pozitiv intr‑o varianta iterativa si una recursiva.Algoritmul de calcul se bazeaza pe aflarea cifrelor numarului prin impartiri la 10. procedura INV1(n)este:

{iterativ} repeta │ scrie n mod 10 │ n=n div 10; └ pana n=0 sfarsit procedura INV2(n)este:

{recursiv} scrie n mod 10 daca (n div 10)<>0 atunci

│

INV2(n div 10) └ sfarsit Programul principal:  n=12345

INV1(n); INV2(n); stop

04/12/2313

Programul in C:#include<stdio.h>const n=1234;/*functia iterativa*/void invi(int n){

do{

printf("%d",n%10);

n=n/10;

}while(n>0);}/*functia recursiva*/void invr(int n){

printf("%d", n%10);

if(n/10!=0) invr(n/10);}void main(){

invr(n);

printf("\n");

invi(n);}

04/12/2314

Exemplul 3. Sa se determine cel mai mare divizor comun a doua numere folosind o varianta recursiva si una iterativa pentru algoritmul lui Euclid. In varianta iterativa se va folosi algoritmul lui Euclid in varianta clasicia iar in varianta recursiva se va folosi definitia: a

daca a=bcmmdc(a,b)= cmmdc(b,a mod b) daca a<> b  functia CMMDCR(a,b) este: daca b=0 atunci

│

CMMDC=a

│ altfel

│

CMMDCR=CMMDCR(b,a mod b);

└ sfarsit functia CMMDCI(a,b) este:

daca a<b atunci

│

r=a;

│

a=b;

│

b=r;

└

r= a mod b;

cat timp r<>0 executa

│

a=b;

│

b=r;

│

r= a mod b;

└

CMMDCI:=a; sfarsit

 

04/12/2315

Programul principal:scrie ’ dati numerele:'citeste a,bc:=CMMDCR(a,b);scrie'CMMDCR=',cc:=CMMDCI(a,b);scrie 'CMMDCI=',cstop

04/12/2316

Programul in C:#include <stdio.h>#include <conio.h>/* functia recursiva*/int cmmdcr(int a,int b){

if (b==0) return a;

else

return cmmdcr(b,a%b);}/* functia iterativa*/int cmmdci(int a, int b){

int r;

r=a%b;

while (r!=0){

a=b;

b=r;

r=a%b;

}return b;}void main(){

clrscr();printf(" Cmmdcr( %d,%d)=%d\n Cmmdci(%d,%d)=%d",72,48,

Cmmdcr(72,48),72,48,cmmdci(72,48));

getchar();}

04/12/2317

. Sa se calculeze primele n numere din sirul lui Fibonacci folosind o varianta recursiva si una iterativa.

Sirul numerelor lui Fibonacci 0, 1, 1, 3, 5, 8, 13, 21, ... sunt definite recursiv astfel:f(0)=0, f(1)=1,

f(i)=f(i-1)+f(i-2) pentru i>1.  functia fiboi (n) este:

// varianta iterativa

i=1

a=0

b=1

daca(n<=1) atunci

│

fiboi=n

│altfel

│ cat timp (i<=n) repeta

│

│

c=a+b

│

│

a=b

│

│

b=c

│

│

i=i+1

│

└

│

fiboi=c

└ stop functia fibor (n) este:

// varianta recursiva

daca(n<=1) atunci

│

fibor=n

│altfel

│

fibor=fibor(n-1)+fibor(n-2)

└ stop 

citeste n

pentru i=1,n,1 repeta

scrie fiboi(i), fibor(i)

stop 

04/12/2318

Programul in C:#include <stdio.h>int fiboi(int n);int fibor(int n);void main(){int n,i;printf("dati n"); scanf("%d",&n);printf(" i fiboi(i) fibor(i)\n\n");for (i=0;i<=n;i++) printf(" %d %d %d\n",i,fiboi(i),fibor(i));getch();}int fiboi(int n){ int i=1,a=0,b=1,c; if(n<=1) return n; else{

while(i<n){c=a+b;a=b;b=c;i++;

}return c;

} }int fibor(int n){ if(n<=1) return n; else

return fibor(n-1)+fibor(n-2);}

04/12/2319

Observatie.De obicei se asociaza o multime de entitati locale unui subprogram, adica

variabile, constante, tipuri care sunt definite local in acel subprogram si care nu au nici o semnificatie in afara ei. In acest caz de fiecare data cand un asemenea subprogram este activat recursiv, se creaza un nou set de variabile locale. Desi noile variabile au acelasi nume cu cele existente inainte de activarea subprogramului, valorile lor sunt distincte si orice conflict de nume este evitat de regulile domeniului de valabilitate al identifica torilor: Identificatorii se refera intotdeauna la ultimul set de variabile creat. Aceleasi reguli se refera si la parametrii de tip valoare ai subprogramului, care sunt inglobati prin definitie in subprogram.

Este indicat pe cat posbil a nu se folosi variabile locale in subprograme recursive pentru a nu se depasi stiva procesorului.

04/12/2320

Exemplul 5. Sa se afiseze in ordine inversa un sir de caractere de lungime arbitrara, terminat prin spatiu.Algoritmul recursiv in pseudocod::procedura INVSIR() este: citeste ch daca ch<> ’ ’ atunci INVSIR(); scrie chsfarsitProgramul principal:scrie’ sirul este’INVSIR()stop Programul in C: #include <stdio.h>#include<conio.h>void invsir(){

char ch;

if((ch=getchar())!=' ') invsir();

putchar(ch);} void main(){

printf("Dati sirul terminat cu spatiu liber:\n");

invsir();} 

04/12/2321

Pentru fiecare apel al procedurii recursive INVSIR se creaza o copie a variabilei locale "ch".

Recursivitatea poate fi transformata in majoritatea cazurilor intr‑o iteratie. In general, forma nerecursiva a unui program este mai eficienta decit cea recursiva in ceea ce priveste timpul de executie si memoria ocupata.

In alegerea caii recursive sau iterative de a rezolva o problema, programatorul trebuie sa‑si stabileasca bine priorita tile in alcatuirea programului, analizand complexitatea acestuia, naturaletea exprimarii, usurinta proiectarii si intretinerii programului, eficienta in executie.

Daca problema de rezolvat este de complexitate redusa si programul trebuie sa aiba eficienta maxima, iar transformarea recursivitatii in iteratii se face usor fara a dauna asupra natu raletii algoritmului, este de preferat varianta iterativa (ca in exemplele de mai sus).

In general, clasa de functii definite recursiv:

G(x) , daca n=0 Fn(x)= H * Fn‑1(x) , daca n>0 se poate exprima iterativ, solutia recursiva nefiind absolut necesara.

Pentru a nu se crea la fiecare apel recursiv multe copii de variabile locale, se indica, atunci cand acest lucru este posibil, folosirea variabilelor declarate global.

04/12/2322

Astfel, in programul urmator care determina recursiv maximul unui sir, variabilele k, j, s‑au declarat globale si nu locale. 

Exemplul 6. Sa se determine maximul unui sir de numere intregi folosind o solutie recursiva.

functia maxr(i) este:

daca i<n atunci

│

daca a[i]>a[j] atunci

│ │

k=i

│ │altfel

│ │

k=j

│ └

│ altfel

│

k=n

│

maxr=k

└

sfarsit 

Programul principal:

citeste n

citeste a(i),i=1,n

scrie "Rangul elementului maxim=”,maxr(1)

scrie “Valoarea sa este”, a[maxr(1)]

stop

04/12/2323

Programul in C: #include <stdio.h>#define NMAX=6;int a[6]={1,4,2,5,9,15};int i,j,k,n=6;int maxr(int i){

if (i<n-1){

j=maxr(i+1);

if (a[i]>a[j])

k=i;

else k=j;

}

else

k=n-1;

return k; }void main(){

printf("Rangul elementului maxim=%d\n Valoarea sa este %d\n", maxr(2)+1,a[maxr(2)]);}

04/12/2324

Exemplul 7. O functie recursiva este adecvata in problema partitiilor unui numar natural n. Prin partitiile unui numar natural n, se intelege totalitatea posibilitatilor de exprimare ale unui numar natural n ca o suma de alte numere naturale, fiecare dintre ele nedepasind o valoare data m.

1,

daca m=1 sau n=1 P(n,m)=

1+P(n,n‑1)

daca n<=m P(n,m‑1)+P(n‑m,m) daca n>m 

De exemplu partitiile numarului 5 din numere ce nu depasesc 3 se vor calcula astfel:

P(5,2)=P(5,1)+P(3,2) P(5,1)=1

P(3,2)=P(3,1)+P(1,2)

=>P(5,3)=1+1+1+1+1=5 P(3,1)=1 P(1,2)=1 P(2,3)=1+P(2,1) P(2,1)=1

Intr‑adevar, exista 5 posibilitati de a exprima numarul 5 ca sume de numere naturale ce nu depasesc valoarea 3: 1+1+1+1+1 , 1+1+1+2 , 1+1+3 , 1+2+2, 2+3.

In timp ce proiectarea unui algoritm nerecursiv pentru calcu lul acestei functii este destul de greoaie, necesitand crearea unei stive pentru memorarea argumentelor si valorilor functiei, varianta recursiva este imediata.

Atasand o functie numarului de partitii, valoarea functiei este data de urmatoarea regula:

P(5,3)=P(5,2)+P(2,3)

04/12/2325

Algoritmul in pseudocod:functia PART(n,m) este daca (m=1) or (n=1) atunci PART=1 altfel daca n<=m atunci PART=1+PART(n,n‑1) altfel PART=PART(n,m‑1)+PART(n‑m,m);sfarsitciteste n,mscrie (PART(n,m));stop Programul in C: #include <stdio.h>#include<conio.h>int partitii(int n, int m){

if((m==1) || (n==1)) return 1;

else if (n<=m) return (1+partitii(n,n-1));

else return ( partitii(n,m-1)+partitii(n-m,m));}void main(){

int n,m;

printf("\nDati n si m\n");

scanf("%d",&n);

scanf("%d",&m);

printf("%d\n",partitii(n,m));}

04/12/2326

2. O altă funcţie recursivă cunoscută este funcţia lui Ackermann definită astfel: A(0,n)=n+1 A(m,0)=A(m‑1,1) A(m,n)=A(m‑1,A(m,n‑1))Pentru câteva valori particulare ale argumentelor, valorile acestei funcţii sunt cunoscute:

A(1,n)=n+2; A(2,n)=2*(n+3)‑3; A(3,n)=2n+3‑3.

Datorită gradului mare de recursivitate a acestei funcţii, ea este frecvent folosită ca un criteriu de evaluare a performanţelor compilatoarelor, indicând eficienţa mecanismului de apel al proce durilor recursive.

Recursivitate indirectă În cazul recursivităţii indirecte, există cel puţin un apel al unei proceduri

care nu a fost încă declarată. Cum în Pascal, declararea procedurilor trebuie să preceadă folosirea lor, această situaţie se rezolvă printr‑o declarare fictivă ce precede declara rea propriu-zisă şi care are forma: antet procedura;FORWARD;

Parametrii formali specificaţi în declaraţia fictivă a proce durii sau funcţiei, nu se vor mai specifica la declararea ei propriu‑zisă.

04/12/2327

Schema generală pentru recursivitatea indirecta este:

procedure Q (lista de parametrii formali);FORWARD; procedure P (lista de parametrii formali); ............................................. begin ................. Q (lista de parametrii actuali) .................................. end; {P} procedure Q ...................... begin .................. P(lista parametrii actuali) ................................. end; {Q}

In Pascal.

04/12/2328

In C problema recursivitatii indirecte se rezolva prin predefinirea functiilor la inceputul programului si definirea lor propriu-zisa dupa definirea functiei main(). Schema generală pentru recursivitatea indirecta este: procedure Q (lista de parametrii formali);

procedure P (lista de parametrii formali); ............................................. begin ................. Q (lista de parametrii actuali) .................................. end; {P} procedure Q ...................... begin .................. P(lista parametrii actuali) ................................. end; {Q}

04/12/2329

Exemplul 1: Să se simuleze operaţiile unui calculator de birou care calculează expresii şi livrează rezultatul.

Exemplul ilustrează maniera de programare TOPDOWN (prin rafinare succesivă). Sintaxa expresiilor care se calculează, se exprimă în felul următor:

04/12/2330

04/12/2331

Daca se scrie cate o functie pentru expresie, termen, factor se obserca ca functia pentru expresie va apela functia terrmen, functia termen va apela functia factor iar functia factor va apela functia expresie- recursivitate indirecta.Exemple de astfel de expresii de calculat sunt: 130/(20+3*15), 83.5+3*7, 169+2/3;

O expresie poate conţine termeni aditivi şi factori, iar un factor la rândul lui poate fi o expresie şi astfel expresiile se definesc recursiv.

O primă formulare a algoritmului în pseudocod poate fi: start citeşte(caracterurmator) ┌ cât timp caracterurmator <> ',' si caracterurmator<>';‘ repeta │ 1*citeşte o expresie, calc rezultatul şi citeşte │ caracterul următor în variabila carurm │ *scrie rezultatul │ └─────▄ stop.

04/12/2332

Rafinând 1 se obţine: procedura CITEXPR (exprcar, valexpr) este 2*citeşte un termen, calculează valoarea lui în valexpr şi citeşte următorul caracter în exprcar cât timp (exprcar='+') sau (exprcar='─') execută │ opaditiv<-exprcar │ citeste exprcar │ 2* citeşte un termen, calculează valoarea lui în │ valtermurm şi citeşte următorul caracter în exprcar │ dacă opaditiv='+' atunci │ │ valexpr <- valexpr+valtermurm │ │ altfel valexpr <- valexpr-valtermurm │ │ │ └────▄ │ └───────────▄ sfârşit

04/12/2333

Rafinând 2 se obţine: procedura CITERM (termcar, valterm) este 3* citeşte un factor, calculează valoarea lui în valterm şi citeşte următorul caracter în termcar cât timp (termcar='*') sau (termcar='/') execută │ opmul termcar │ citeşte termcar │ 3* citeste un factor,calculeaza valoarea lui în │ valfacturm şi citeste urmatorul caracter în termcar │ dacă opmul='*' atunci valterm<-valterm*valfacturm │ │ altfel │ │ valterm <- valterm/valfacturm │ │ │ └────▄ └──────────────▄ sfârşit

04/12/2334

Rafinând 3 se obţine: procedura CITNUM (numcar, valnum) este valnum <- 0 cât timp * numcar este cifra execută │ valnum <- 10*valnum+cifra │ citeşte numcar └─────────▄ ┌ dacă numcar='.' atunci citeşte numcar │ scara < - 0 │ cât timp *numcar este cifra execută │ │ valnum <- 10*valnum+cifra │ │ citeşte numcar │ │ scara scara+1 │ └──────────▄ └──────────────────▄ valnum ,- valnum/10scara sfârşit

04/12/2335

Trebuie luate în considerare şi erorile ce pot apare la introducerea expresiilor. Pot fi depistate 4 tipuri de erori: 1) lipseşte paranteza dreaptă după o expresie precedată de o paranteză stânga; 2) lipseşte virgula după o expresie; 3) s-a detectat un caracter ilegal într-un factor; 4) s-a detectat o împărţire la zero; Aceste 4 tipuri de erori se tratează astfel: 1) Erorile vor fi semnalate prin indicarea poziţiei carac terului ce a provocat eroarea.

În acest scop, caracterele tastate se numerotează şi deci pentru citirea unui caracter se va folosi o procedură care numără caracterele citite. După semnalarea unei erori se ignoră toate caracterele citite. 2) Citirea unui caracter se poate face cu o procedură care să ignore eventualele blancuri ce pot separa caracterele. Astfel, pentru claritate pot fi introduse blancuri în introducerea expre siilor: 5+4* (21+27─129) 3) Se permite terminarea unei expresii la sfârşitul unui rând. Astfel, dacă după o expresie se detectează caracterul eoln, el se modifică în virgulă. 5+3*8, 21+83*(7+139), 34+91..... 5+3*8 21+83*(7+138) 34+29*.....

04/12/2336

4)Dacă la sfârşitul tuturor expresiilor se omite ';' şi se întâlneşte EOF(CTRL+Z), atunci caracterul se transformă în ';'. Cu aceste observaţii, pentru a citi un caracter se foloseşte o proce dură al cărui pseudocod este: procedura CITCAR (ch, pozcar)este repetă │ dacă EOF atunci ch ';'; │ │ altfel │ │ dacă EOLN atunci │ │ │ pozcar 0 │ │ │ ch <- ',' │ │ │ * salt la următoarea linie │ │ │ altfel pozcar <- pozcar+1 │ │ │ citeşte ch │ │ │ │ │ └─────────▄ │ │ │ └────────────▄ │ └────────▄ până ch <> ' '

04/12/2337