Capitolul IB.06. Funcţii. Definire şi utilizare în limbajul...

INFORMATIC*I* IB.06. Funcii. Definire i utilizare n limbajul C

- 1 -

Capitolul IB.06. Funcii. Definire i utilizare n limbajul C

Cuvinte cheie Subrutin, top down, funcie apelat, funcie apelant, parametri,

argumente, definire funcii, funcii void, declarare funcii, domeniu

de vizibilitate (scope), apel funcie, instruciunea return, transmiterea

parametrilor, funcii cu argumente vectori, recursivitate

IB.06.1. Importana funciilor n programare

n unele cazuri, o anumit poriune de cod este necesar n mai multe locuri (puncte) ale

programului. n loc s repetm acel cod n mai multe locuri, este preferabil s-l reprezentm ntr-o

aa numit subrutin i s chemm (apelm) aceast subrutin n toate punctele programului n

care este necesar execuia acelui cod. Acest lucru permite o mai bun nelegere a programului,

uureaz depanarea, testarea i eventuala sa modificare ulterioar. n C/C++ subrutinele se numesc

funcii.

Funcia este un concept important n matematic i programare. n limbajul C prelucrrile sunt

organizate ca o ierarhie de apeluri de funcii. Orice program trebuie s conin cel puin o funcie,

funcia main.

Funciile ncapsuleaz prelucrri bine precizate i pot fi reutilizate n mai multe programe. Practic,

nu exist program care s nu apeleze att funcii din bibliotecile existente ct i funcii definite n

cadrul aplicaiei respective. Ceea ce numim uzual program sau aplicaie este de fapt o colecie de

funcii (subprograme).

Motivele utilizrii funciilor sunt multiple:

Evit repetarea codului: este uor s faci copy i paste, dar este greu s menii i s sincronizezi

toate copiile;

Utilizarea de funcii permite dup cum spuneam dezvoltarea progresiv a unui program mare, fie de jos n sus (bottom up), fie de sus n jos (top down), fie combinat. Astfel, un

program mare poate fi mai uor de scris, de neles i de modificat dac este modular, adic

format din module funcionale relativ mici;

O funcie poate fi reutilizat n mai multe aplicaii - prin adugarea ei ntr-o bibliotec de funcii - ceea ce reduce efortul de programare al unei noi aplicaii;

O funcie poate fi scris i verificat separat de restul aplicaiei, ceea ce reduce timpul de punere la punct al unei aplicaii mari (deoarece erorile pot apare numai la comunicarea ntre

subprograme corecte);

De ce discutam acum despre funcii? Deoarece programele prezentate n continuare vor

crete n complexitate, aa nct, pentru dezvoltarea lor, vom aplica tehnica de analiza i

proiectare Top Down sau Stepwise Refinement ce cuprinde urmtorii pai:

1. problema se descompune n subprobleme - n pai de prelucrare

2. fiecare subproblem poate fi descompus la rndul su n alte subprobleme

3. fiecare subproblem este implementat ntr-o funcie

4. aceste funcii sunt apelate n main, ceea ce va duce la execuia pe rnd a pailor

necesari pentru rezolvarea problemei.


- 2 -

ntreinerea unei aplicaii este simplificat, deoarece modificrile se fac numai n anumite funcii i nu afecteaz alte funcii (care nici nu mai trebuie recompilate);

Standardul limbajului C conine o serie de funcii care exist n toate implementrile limbajului.

Declaraiile acestor funcii sunt grupate n fiiere antet cu acelai nume pentru toate

implementrile. n afara acestor funcii standard exist i alte biblioteci de funcii: funcii specifice

sistemului de operare, funcii utile pentru anumite aplicaii (grafic, baze de date, aplicaii de reea

.a.).

Dou entiti sunt implicate n utilizarea unei funcii: un apelant, care apeleaz (cheam) funcia i

funcia apelat. Apelantul, care este i el o funcie, transmite parametri (numiti i argumente)

funciei apelate. Funcia primete aceti parametri, efectueaz operaiile din corpul funciei i

returneaz rezultatul/rezultatele napoi funciei apelante.

Comunicarea de date ntre funcii se face de regul prin argumente i numai n mod excepional prin

variabile externe funciilor vezi domeniu de definiie.

Exemplu

S presupunem c avem nevoie s evalum aria unui cerc de mai multe ori (pentru mai multe valori

ale razei). Cel mai bine este s scriem o funcie numit calculAria(), i s o folosim cnd avem

nevoie. #include

#include

// prototipul funciei (declararea)

double calculAria (double);

int main() {

double raza1 = 1.1, aria1, aria2;

// apeleaza functia calculAria:

aria1 = calculAria (raza1);

printf(Aria 1 este %lf\n ", area1);


aria2 = calculAria (2.2);

printf(Aria 2 este %lf\n ", area2);


printf(Aria 3 este %lf\n ", calculAria (3.3));

return 0;

}

// definirea functiei

double calculAria (double raza) {

return raza* raza*M_PI; // M_PI definit in biblioteca math

Funcia APELANT

c = max(a,b);

Funcie APELAT

int max(int n1, int n2){

return (n1>n2)?n1:n2;

}

Rezultate

Parametri


- 3 -

}

n acest exemplu este definit o funcie numit calculAria care primete un parametru de tip double

de la funcia apelant n acest caz main-ul efectueaz calculul i returneaz un rezultat, tot de tip

double funciei care o apeleaz. n main, funcia calculAria este chemat de trei ori, de fiecare dat

cu o alt valoare a parametrului.

IB.06.2. Definirea i utilizarea funciilor

Pentru a putea fi utilizat ntr-un program, definiia unei funcii trebuie s precead utilizarea

(apelarea) ei.

Forma general a unei definiii de funcie, conform standardului, este:

unde:

tip_rezultat_returnat este tipul rezultatului returnat de funcie. n limbajul C o parte din funcii au o valoare ca rezultat iar altele nu au(sunt de tip void). Pentru o funcie cu rezultat

diferit de void tipul funciei este tipul rezultatului funciei. Tipul unei funcii C poate fi orice

tip numeric, orice tip pointer, orice tip structur (struct) sau void.

Dac tip_rezultat_returnat este: int - funcia este ntreag

void - funcia este void

float - funcia este real.

Lista parametrilor formali cuprinde declaraia parametrilor formali, separai prin virgul:

Sintaxa:

lista_parametri_formali = tip_p1 nume_p1, tip_p2 nume_p2, ..., tip_pn nume_pn

unde:

tip_p1, tip_p2,., tip_pn sunt tipurile parametrilor formali nume_p1, nume_p2, ..., nume_pn sunt numele parametrilor formali

Exemple:

1. S se calculeze i s se afieze valoarea expresiei xm+yn+(xy)m^n , x, y, m, n fiind citii de la tastatur, astfel nct ntregii m,n s fie pozitivi. Ridicarea la putere se va realiza printr-o

funcie putere care primete baza i exponentul ca parametri i returneaz rezultatul.

Modul n care se va apela (folosi) aceasta funcie l vom arta la Apelul unei funcii.

Rezultatul va fi: Aria 1 este 3.80134

Aria 2 este 15.2053

Aria 3 este 34.212

Sintaxa:

tip_rezultat_returnat nume_functie (lista_parametri_formali) {

/* corpul functiei: */

definirea variabilelor locale //declaraii

prelucrari // instructiuni

}


- 4 -

2. Numrarea i afiarea numerelor prime mai mici ca un ntreg dat n. Pentru aceasta vom scrie o funcie care testeaz dac un numr este prim. Modul n care se va apela (folosi) aceast funcie

l vom arta la Apelul unei funcii.

Parametrii formali sunt vizibili doar n corpul funciei care i definete. Prin parametrii formali, funcia

primete datele iniiale (de intrare) necesare i poate transmite rezultate. Parametrii formali pot fi

doar nume de variabile, adrese de variabile (pointeri) sau nume de vectori, deci nu pot fi expresii

sau componente de vectori.

Observaii:

Definiiile funciilor nu pot fi incluse una n alta ( ca n Pascal ).

Se recomand ca o funcie s ndeplineasc o singur sarcin i s nu aib mai mult de cteva zeci de linii surs (preferabil sub 50 de linii).

Este indicat ca numele unei funcii s fie ct mai sugestiv, poate chiar un verb (denot o aciune) sau o expresie ce conine mai multe cuvinte neseparate ntre ele. Primul cuvnt este scris

cu liter mic, n timp ce restul cuvintelor sunt scrise cu prima liter mare.

Exemple: calculAria(), setRaza(), mutaJos(), ePrim(), etc.

Funcii void

S presupunem c avem nevoie de o funcie care s efectueze anumite aciuni (de exmplu o

tiprire), fr s fie nevoie s returneze o valoare apelantului. Putem declara aceast funcie ca fiind

de tipul void.

Dac funcia nu returneaz nici un rezultat dar primete parametri, definiia va fi:

// functia care calculeaza bazaexp

double putere (double baza, int exp){

int i; //declarare variabila locale

float rez; //declarare variabila locale

//instructiuni:

for(i=rez=1;i


- 5 -

Dac funcia nu returneaz nici un rezultat i nu primete parametri, definiia va fi:

Observaie: o funcie void poate ntoarce rezultatele prelucrrilor efectuate prin parametri.

IB.06.3. Declararea unei funcii

O funcie trebuie s fie declarat nainte de utilizare. Putem realiza acest lucru n dou moduri:

- amplasnd n textul programului definiia funciei naintea definiiei funciei care o apeleaz -

main sau alta funcie

- declarnd prototipul (antetul) funciei nainte de definiia funciei care o apeleaz; n acest caz,

definiia funciei poate fi amplasat oriunde n program.

Cu alte cuvinte, dac funcia este definit dup funcia n care este apelat, atunci este necesar o

declaraie anterioar a prototipului funciei.

Declaraia unei funcii se face prin precizarea prototipului (antetului) funciei:

n prototip, numele parametrilor formali pot fi omii, aprnd doar tipul fiecruia.

Exemple: // prototip funcie, plasat naintea locului n care va fi utilizat

double calculAria(double); // fr numele parametrilor

int max(int, int);

/* Numele parametrilor din antet vor fi ignorate de compilator dar vor

servi la documentare: */

double calculAria(double raza);

int max(int numar1, int numar2);

Antetele funciilor sunt uzual grupate mpreun i plasate ntr-un aa numit fiier antet (header file).

Acest fiier antet poate fi inclus n mai multe programe.

Exemple:

O funcie max(int, int), care primete dou numere ntregi i ntoarce valoarea maxim. Funcia max

este apelat din main.

Sintaxa:

tip_rezultat_returnat nume_functie (lista_parametri_formali);

Sintaxa:

void nume_functie ( ) {




}

Sintaxa:

void nume_functie (lista_parametri_formali) {




}


- 6 -

Cu alte cuvinte, n lipsa unei declaraii de tip explicite se consider c tipul implicit al funciei este

int.

i argumentele formale fr un tip declarat explicit sunt considerate implicit de tipul int, dar nu

trebuie abuzat de aceast posibilitate.

Exemplu:

n limbajul C se pot defini i funcii cu numr variabil de argumente, care pot fi apelate cu numr

diferit de argumente efective.

Mai jos apar dou variante de scriere a programelor. Prima variant, n care funcia main e prezent

la nceputul programului, dup prototipurile funciilor apelate, ofer o imagine a prelucrrilor

realizate de program.

Prototipul implicit al unei funcii, este:

int nume_functie(void);

rest (a,b) { //echivalent cu: int rest (int a, int b)

return a%b;

}

// functia lines definit dup main, dar declarat nainte:

void lines ( int); // declaraie funcie

int main () {

lines (3); // utilizare funcie

}

void lines (int n) {

for (int i=0; i


- 7 -

IB.06.4. Domeniu de vizibilitate (scope)

n C/C++ exist urmtoarea convenie :

Prin urmare, avem ca regul de baz: identificatorii sunt accesibili doar n blocul de instruciuni n

care au fost declarai; ei sunt necunoscui n afara acestor blocuri.

Locul unde este definit o variabil determin domeniul de vizibilitate al variabilei respective: o

variabil definit ntr-un bloc poate fi folosit numai n blocul respectiv, iar variabilele cu acelai

nume din funcii (blocuri) diferite sunt alocate la adrese diferite i nu nici o legtur ntre ele.

Numele unei variabile este unic (nu pot exista mai multe variabile cu acelai nume), dar o variabil

local poate avea numele uneia globale, caz n care, n interiorul funciei, e valabil noua

semnificaie a numelui.

Pentru variabilele locale memoria se aloc la activarea funciei/blocului (deci la execuie) i este

eliberat la terminarea executrii funciei/blocului. Iniializarea variabilelor locale se face tot la

execuie i de aceea se pot folosi expresii pentru iniializarea lor (nu numai constante).

Exemple: #include

#include

int fact=1; // declarare varriabila externa - globala

void factorial(int n) // parametru formal

{ int i; // declarare variabila locala

fact=1;

for(i=2;i


- 8 -

// utilizare variabila locala:

scanf("%d",&v);

factorial(v);

printf("%d!=%d\n",v,fact);

return 0;

}

Atenie! Definiia unui identificator mascheaz pe cea a aceluiai identificator declarat ntr-un

suprabloc sau n fiier (global)! Apariia unui identificator face referin la declararea sa n

cel mai mic bloc care conine aceast apariie!

#include

#include

int fact=1; // declarare variabila externa - globala

void factorial(int n)

{

int i; // declarare variabila locala

int fact=1; /* declarare variabila locala, acesta

va fi folosita in functie mai departe! */

for(i=2;i


- 9 -

Observaii:

Parametrii folosii la apelul funciei se numesc parametri efectivi i pot fi orice expresii (constante,

funcii etc.). Parametrii efectivi trebuie s corespund ca numr i ca tipuri (eventual prin conversie

implicit ) cu parametrii formali (cu excepia unor funcii cu numr variabil de argumente).

Este posibil ca tipul unui parametru efectiv s difere de tipul parametrului formal corespunztor, cu

condiia ca tipurile s fie "compatibile" la atribuire. Conversia de tip (ntre numere sau pointeri) se

face automat, la fel ca la atribuire:

n cazul funciilor void fr parametri, apelul se face prin:

La apelul unei funcii, pe stiva de apeluri (pstrat de Sistemul de Operare) se creaz o nregistrare

de activare, care cuprinde, de jos n sus:

adresa de revenire din funcie

valorile parametrilor formali

valorile variabilelor locale.

n momentul apelrii unei funcii, se execut corpul su, dup care se revine n funcia apelant, la

instruciunea urmtoare apelului.

Revenirea dintr-o funcie se face fie la ntlnirea instruciunii return, fie la terminarea execuiei

corpului funciei (funcia poate s nu conin instruciunea return doar n cazul funciilor void).

Exemple - apelul funciilor putere i prim:

1. S se calculeze i s se afieze valoarea expresiei xm+yn+(xy)m^n , x, y, m, n fiind citii de la tastatur, astfel nct ntregii m,n s fie pozitivi. Ridicarea la putere se va realiza printr-o funcie

putere care primete baza i exponentul ca parametri i returneaz rezultatul vezi definirea

unei funcii. Modul de apel al funciei putere:

int main(void){

int m,n;

double x,y;

while( printf(" m(>=0):"), scanf("%d",&m), m


- 10 -

while( printf(" n(>=0):"), scanf("%d",&n), n


- 11 -

Observaii:

O funcie de un tip diferit de void trebuie s conin cel puin o instruciune return prin care se transmite rezultatul funciei:

Compilatoarele C nu verific i nu semnaleaz dac o funcie de un tip diferit de void conine sau nu instruciuni return, iar eroarea se manifest la execuie.

Cuvntul else dup o instruciune return poate lipsi, dar de multe ori este prezent pentru a face

codul mai clar.

Exemplu fr else: // transforma caracterul din variabila c in liter mare

char toupper (char c) {

if (c>='a' && c


- 12 -

Observaii:

Dac se dorete ca o funcie s modifice valoarea unei variabile, trebuie s i se transmit pointerul la variabila respectiv - vezi Pointeri!

Dac parametrul este un tablou, cum numele este echivalent cu pointerul la tablou, funcia poate modifica valorile elementelor tabloului, primind adresa lui. A se observa c trebuie s se

transmit ca parametri i dimensiunea/ dimensiunile tabloului.

Dac parametrul este ir de caractere, dimensiunea tabloului de caractere nu trebuie s se transmit, sfritul irului fiind indicat de caracterul terminator '\0'.

IB.06.8. Funcii cu argumente vectori

Pentru argumentele formale de tip vector nu trebuie specificat dimensiunea vectorului ntre

parantezele drepte, oricum aceasta va fi ignorat.

Exemplu: // calcul valoare maxima dintr-un vector:

float maxim (float a[], int n ) {

float max=a[0];

for (int k=1;k


- 13 -

Un argument formal vector poate fi declarat i ca pointer, deoarece are ca valoare adresa de nceput

a zonei unde este memorat vectorul.

Exemplu:

De remarcat c pentru un parametru efectiv vector nu mai trebuie specificat explicit c este un

vector, deoarece exist undeva o declaraie pentru variabila respectiv, care stabilete tipul ei. Este

chiar greit sintactic s se scrie:

O funcie C nu poate avea ca rezultat direct un vector, dar poate modifica elementele unui vector

primit ca parametru.

Exemplu de funcie pentru ordonarea unui vector prin metoda bulelor Bubble Sort:

void sort (float a[ ], int n) {

int n,i,j, gata;

float aux;

do {

gata = 1;// presupunem initial ca nu sunt necesare schimbari de elemente

for (i=0;i a[i+1] ) {// daca nu sunt in ordine crescatoare

aux=a[i];

a[i]=a[i+1];

a[i+1]=aux;

// am interschimbat a[i] cu a[i+1]

gata =0;

// seteaza ca s-a facut o schimbare

}

} while (!gata); // repeta cat timp au mai fost schimbari de elemente

}

Probleme pot apare la parametrii efectivi de tip matrice din cauza interpretrii diferite a zonei ce

conine elementele matricei de ctre funcia apelat i respectiv de funcia apelant. Pentru a

interpreta la fel matricea liniarizat este important ca cele dou funcii s foloseasc acelai numr

de coloane n formula de liniarizare. Din acest motiv nu este permis absena numrului de coloane

din declaraia unui parametru formal matrice.

O alt soluie la problema parametrilor matrice este utilizarea de matrice alocate dinamic i

transmise sub forma unui pointer.

O sintez a transmiterii parametrilor de tip tablou este dat n cele ce urmeaz:

xmax = maxim ( x[ ], 7 ) ; // NU !

Exemple:

void printmat(int a[][10], int nl, int nc); // corect, cu nc


- 14 -

Parametru formal Parametru actual

tip_baza nume_vector[]

tip_baza nume_ vector[dim]

nume_vector

tip_baza nume_ matrice[][dim2]

//dim2 trebuie sa apara

tip_baza nume_ matrice[dim1][dim2]

nume_matrice

IB.06.9. Funcii recursive

n continuare se va prezenta conceptul de recursivitate i cteva exemple de algoritmi recursivi,

pentru a putea nelege mai bine aceast tehnic puternic de programare, ce permite scrierea unor

soluii clare, concise i rapide, care pot fi uor nelese i verificate.

IB.06.9.1 Ce este recursivitatea ?

Un obiect sau un fenomen se definete n mod recursiv dac n definiia sa exist o referire la el nsui.

Recursivitatea este folosit cu multa eficien n matematic. Spre exemplu, defintii matematice

recursive sunt:

Utilitatea practic a recursivitii rezult din posibilitatea de a defini un set infinit de obiecte printr-

o singur relaie sau printr-un set finit de relaii.

Recursivitatea s-a impus n programare odat cu apariia unor limbaje de nivel nalt, ce permit

scrierea de module ce se autoapeleaz (PASCAL, LISP, ADA, ALGOL, C sunt limbaje recursive,

spre deosebire de FORTRAN, BASIC, COBOL, nerecursive).

Recursivitatea este strns legat de iteraie. Iteraia este execuia repetat a unei poriuni de

program, pn la ndeplinirea unei condiii (exemple: while, do-while, for din C).

Definiia numerelor naturale:

0 N

dac i N, atunci succesorul lui i N

Definiia funciei factorial fact : N -> N

fact (n) = 1, daca n=0

n * fact (n-1), daca n>0

Definiia funciei Ackermann ac: N x N -> N

n+1, dac m=0

ac(m,n) = ac(m-1,1), dac n=0

ac(m-1, ac(m,n-1) ), dac m, n >0

Definiia funciei Fibonacci fib : N -> N

fib(n) = 1, dac n=0 sau n=1

fib(n-2) + fib(n-1), dac n>1


- 15 -

Recursivitatea presupune execuia repetat a unui modul, ns n cursul execuiei lui (i nu la sfrit,

ca n cazul iteraiei), se verific o condiie, a crei nesatisfacere implic reluarea execuiei

modulului de la nceput, fr ca execuia curent s se fi terminat. n momentul satisfacerii condiiei

se revine n ordine invers din lanul de apeluri, relundu-se i ncheindu-se apelurile suspendate.

Un program recursiv poate fi exprimat: P = M ( Si , P) , unde M este mulimea ce conine

instruciunile Si i pe P nsui.

Structurile de program necesare i suficiente n exprimarea recursivitii sunt funciile:

Recursivitatea poate fi direct - o funcie P conine o referin la ea nsi, sau indirect - o funcie P

conine o referin la o funcie Q ce include o referin la P. Vom pune accentul mai ales pe funciile

direct recursive.

Se pot deosebi dou feluri de funcii recursive:

Funcii cu un singur apel recursiv, ca ultim instruciune, care se pot rescrie uor sub forma nerecursiv (iterativ).

Funcii cu unul sau mai multe apeluri recursive, a cror form iterativ trebuie s foloseasc o stiv pentru memorarea unor rezultate intermediare.

Recursivitatea este posibil n C datorit faptului c, la fiecare apel al funciei, adresa de revenire,

variabilele locale i argumentele formale sunt puse ntr-o stiv (gestionat de compilator), iar la

ieirea din funcie (prin return) se scot din stiv toate datele puse la intrarea n funcie (se

"descarc" stiva).

Exemplu generic:

Exemplu de funcie recursiv de tip void:

Funcia de mai sus nu scrie nimic pentru n=0, dar poate fi uor completat cu o ramur else la

instruciunea if.

Apelul recursiv al unei funcii trebuie s fie condiionat de o decizie care s mpiedice apelul n

cascad (la infinit ); aceasta ar duce la o eroare de program - depirea stivei.

void p(){ //functie recursiva p(); //apel infinit }

//apelul trebuie conditionat in una din variantele:

if(cond) p(); while(cond) p();

do p() while(cond);

void binar (int n) { // se afieaza n in binar

if (n>0) {

binar(n/2); // scrie echiv. binar al lui n/2

printf("%d",n%2); // i restul impartirii n la 2

}

}

Definiie:

O funcie recursiv este o funcie care se apeleaz pe ea nsi, direct sau indirect.


- 16 -

Anumite funcii recursive corespund unor relaii de recuren.

Exemple: // Calculul an:

double putere (double a, int n) {

if (n==0) return 1.; // a0 = 1

else return a * putere(a, n-1); // an=a*an-1

}

// Algoritmul lui Euclid poate folosi o relaie de recuren:

int cmmdc (int a,int b) {

if ( a%b==0) return b;

return cmmdc( b,a%b); // cmmdc(a,b)=cmmdc(b,a%b)

}

Observaii:

Funciile recursive nu conin n general cicluri explicite (cu unele excepii), iar repetarea operaiilor este obinut prin apelul recursiv. O funcie care conine un singur apel recursiv ca

ultim instruciune poate fi transformat ntr-o funcie nerecursiv, nlocuind instruciunea if

cu while.

Fiecare apel recursiv are parametri diferii, sau mcar o parte din parametri se modific de la un apel la altul.

Se pune ntrebarea: "Ce este mai indicat de utilizat: recursivitatea sau iteraia?" Algoritmii recursivi sunt potrivii pentru a descrie probleme care utilizeaz formule recursive

sau pentru prelucrarea structurilor de date definite recursiv ( liste, arbori ), fiind mai elegani i

mai simplu de neles i verificat. Iteraia este uneori preferat din cauza vitezei mai mari de

execuie i a memoriei necesare la execuie mai reduse. Spre exemplu, varianta recursiv a

funciei Fibonacci duce la 15 apeluri pentru n=5, deci varianta iterativ este mult mai

performant.

Apelul recursiv al unei funcii face ca pentru toi parametrii s se creeze copii locale apelului curent (n stiv) , acestea fiind referite i asupra lor fcndu-se modificrile n timpul execuiei

curente a funciei. Cnd execuia funciei se termin, copiile sunt extrase din stiv, astfel nct

modificrile operate asupra parametrilor nu afecteaz parametrii efectivi de apel,

corespunztori. De asemenea, pentru toate variabilele locale se rezerv spaiu la fiecare apel

recursiv.

Pe parcursul unui apel, sunt accesibile doar variabilele locale i parametrii pentru apelul respectiv, nu i cele pentru apelurile anterioare, chiar dac acestea poart acelai nume!

De reinut c, pentru fiecare apel recursiv al unei funcii se creaz copii locale ale parametrilor

valoare i ale variabilelor locale, ceea ce poate duce la risipa de memorie.

IB.06.9.2 Verificarea i simularea programelor recursive Se face ca i n cazul celor nerecursive, printr-o demonstraie formal, sau testnd toate cazurile posibile:

Pentru funciile de tip diferit de void apelul recursiv se face printr-o instruciune

return, prin care fiecare apel preia rezultatul apelului anterior!

Orice funcie recursiv trebuie s conin cel puin o instruciune if, plasat de obicei chiar la nceput!

Prin aceast instruciune se verific dac mai este necesar un apel recursiv sau se iese din funcie.

Absena instruciunii if conduce la o recursivitate infinit (la un ciclu fr condiie de terminare)!


- 17 -

Se verific nti dac toate cazurile particulare (ce se execut cnd se ndeplinete condiia de terminare a apelului recursiv) funcioneaz corect.

Se face apoi o verificare a funciei recursive, pentru restul cazurilor, presupunnd c toate componentele din codul funciei funcioneaz corect. Verificarea e deci inductiv. Acesta e un

avantaj al programelor recursive, ce permite demonstrarea corectitudinii lor simplu i clar.

Exemplu: Funcia recursiv de calcul a factorialului

Verificarea corectitudinii n acest caz cuprinde doi pai:

1. pentru n=1 valoarea 1 ce se atribuie factorialului este corect

2. pentru n>1, presupunnd corect valoarea calculat pentru predecesorul lui n de ctre fact(n-

1), prin nmulirea acesteia cu n se obine valoarea corect a factorialului lui n.

IB.06.9.3 Utilizarea recursivitatii n implementarea algoritmilor de tip Divide et Impera

Tehnica Divide et Impera, fundamental n elaborarea algoritmilor, const n descompunerea unei

probleme complexe n mai multe subprobleme a cror rezolvare e mai simpl i din soluiile crora

se poate determina soluia problemei iniiale (exemple: gsirea minimului si maximului valorilor

elementelor unui tablou, cutarea binar, sortare Quicksort, turnurile din Hanoi).

Un algoritm de divizare general s-ar putea scrie:

Vom oferi ca exemplu cutarea binar a unei valori v ntr-un vector ordonat a, prin metoda

njumtirii intervalului de cutare. Se returneaz indicele n vector sau -1 dac valoarea v nu se

afl n vector. Pentru o mai bun nelegere, prima variant este cea iterativ.

void rezolva ( problema pentru x ) {

dac x e divizibil in subprobleme {

divide pe x in parti x1,...,xk

rezolva(x1);

...

rezolva(xk);

combina solutiile partiale intr-o solutie pentru x

}

altfel

rezolva pe x direct

}

//varianta recursiva int fact(int n){ if(n==1) return 1; return n*fact(n-1); //apel recursiv }

//varianta nerecursiva

int fact(int n){

int i,f;

for(i=f=1; i=8 (8!>32767)


- 18 -

// varianta iterative, l- limita stanga, r limita dreapta a intervalului

int bsearchIter(int v, int *a, int l, int r) {

while(l a[m]) l=m+1; // reduc intervalul la jumatatea lui dreapta

else r=m; // reduc intervalul la jumatatea lui stanga

}

return -1; // element negasit

}

// varianta recursiva

int bsearchRec (int v, int *a,int l, int r) {

int m;

if (la[m] )

return bsearchRec(v, a, m+1, r);

else

return bsearchRec(v, a, l, m);

}

else return -1;

}

int main() {

int v, a[N], n;

// citire date intrare

printf(Elem. %d se afla in poz %d\n ", v, bsearchRec(v,a,0,n));

printf(Elem. %d se afla in poz %d\n ", v, bsearchIter(v,a,0,n));

return 0;

}

IB.06.10. Anex: Funcii n C++

n C++ toate funciile folosite trebuie declarate i nu se mai consider c o funcie nedeclarat este

implicit de tipul int.

Absena unei declaraii de funcii este eroare grav n C++ i nu doar avertisment ca n C (nu trece

de compilare)!

n C++ se pot declara valori implicite pentru parametrii formali de la sfritul listei de parametri;

aceste valori sunt folosite automat n absena parametrilor efectivi corespunztori la un apel de

funcie. O astfel de funcie poate fi apelat deci cu un numr variabil de parametri.

Exemplu:

// afiare vector, precedat de un titlu (irul primit sau irul nul)

void printv ( int v[], int n, char * titlu="") {

printf ("\n %s \n", titlu);

for (int i=0; i


- 19 -

n C++ funciile scurte pot fi declarate inline, iar compilatorul nlocuiete apelul unei funcii inline

cu instruciunile din definiia funciei, eliminnd secvenele de transmitere a parametrilor. Funciile

inline sunt tratate ca i macrourile definite cu define. Orice funcie poate fi declarat inline, dar

compilatorul poate decide c anumite funcii nu pot fi tratate inline i sunt tratate ca funcii

obinuite. De exemplu, funciile care conin cicluri nu pot fi inline. Utilizarea unei funcii inline nu

se deosebete de aceea a unei funcii normale. Exemplu de funcie inline:

n C++ pot exista mai multe funcii cu acelai nume dar cu parametri diferii (ca tip sau ca numr).

Se spune c un nume este suprancrcat cu semnificaii ("function overloading"). Compilatorul

poate stabili care din funciile cu acelai nume a fost apelat ntr-un loc analiznd lista de parametri

i tipul funciei:

float abs (float f) { return fabs(f); }

long abs (long x) { return labs(x); }

printf ("%6d%12ld %f \n", abs(-2),abs(-2L),abs(-2.5) );

inline int max (int a, int b) { return a > b ? a : b; }

Date post:	28-Mar-2018
Category:	Documents
Upload:	hakien
View:	218 times
Download:	2 times

Capitolul IB.06. Funcţii. Definire şi utilizare în limbajul...

Documents