recursivitatea

Calin Jebelean Recursivitatea 1

Recursivitatea

Recursivitatea este o tehnica de programare care presupune apelarea unui modul de program (procedura, functie) din insusi interiorul sau.Recursivitatea este inrudita cu iteratia, ambele presupunand executii repetate pana la indeplinirea unei conditii sau cat timp o conditie este indeplinitaDe regula, o mare parte a problemelor de rezolvat pot fi gandite recursiv – exemple vor fi date in continuare


Recursivitatea

Sa presupunem ca avem de rezolvat o problema P care depinde de un parametru N, notata P(N)Recursivitatea ne invata ca in rezolvarea problemei P(N), putem presupune ca problema P(N-1) este gata rezolvata, adica aceeasi problema, dar pentru parametrul N-1Tot ce mai avem de facut este sa determinam adaugirile care mai trebuie aduse la rezolvarea problemei P(N-1) pentru a obtine o rezolvare pentru problema P(N)De regula, aceste adaugiri sunt mult mai simplu de gasit decat o rezolvare integrala a problemei P(N)


Recursivitatea

Avem urmatoarea situatie (semnul “” se va citi “se compune din”):P(N) P(N-1) + adaugiriP(N-1) P(N-2) + adaugiriP(N-2) P(N-3) + adaugiri…………………………P(2) P(1) + adaugiriP(1) P(0) + adaugiriP(0) P(-1) + adaugiriP(-1) P(-2) + adaugiri…………………………


Recursivitatea

Evident, nu se ajunge nicaieri printr-o astfel de abordare, deoarece rezolvarea fiecare probleme P(I) se bazeaza pe rezolvarea problemei P(I-1)Dar, daca am cunoaste rezolvarea directa, de exemplu, a problemei P(0) (fara ajutorul lui P(-1)), lucrurile s-ar schimba mult in bineDaca putem rezolva problema P(0), automat putem rezolva si problema P(1)Daca putem rezolva problema P(1), automat putem rezolva si problema P(2)Continuand in acest fel, vom ajunge sa putem rezolva problema P(N)


Recursivitatea

Rezumand, pentru a putea rezolva recursiv o problema P(N) avem nevoie de urmatoarele: problema P(0) sau P(1) sa fie simplu

de rezolvat sa putem exprima rezolvarea

problemei P(N) in functie de rezolvarea problemei P(N-1)


Recursivitatea

Vom studia ca exemplu problema factorialului, care este o problema ce depinde de un parametru NP(N) este: “Sa se gaseasca factorialul numarului N”Pentru rezolvarea problemei P(N) putem presupune ca problema P(N-1) este rezolvataApoi, pentru a afla raspunsul la problema P(N) nu avem decat sa obtinem raspunsul la problema P(N-1) si sa adaugam o inmultire cu NP(0) este: “Sa se gaseasca factorialul numarului 0”Se observa ca problema P(0) este usor de rezolvat si raspunsul sau este 1


Recursivitatea

int factorial(int N){

/* prima data testam daca nu cumva avem de-a face cu problema P(0) careia ii cunoastem raspunsul fara a apela la recursivitate */if (N==0) return 1; /* aceasta este conditia

de oprire a recursivitatii */return N*factorial(N-1); /* in orice alt caz, ne folosim de rezolvarea problemei P(N-1) */

}

Aici este rezolvarea problemei factorial(0)


Recursivitatea

Sa presupunem ca avem o lista simplu inlantuita pe care dorim s-o afisamProblema apare sub forma P(L): “Sa se afiseze elementele listei L”In cazul general, orice lista L este formata dintr-un prim element X urmat de o lista L’ (care contine cu un element mai putin decat L)Pentru a rezolva problema P(L) (afisarea listei L) ar trebui sa-l afisam pe X (primul element al listei L), apoi sa adaugam rezolvarea problemei P(L’) (afisarea listei L’)Nu am facut insa nimic daca nu dam o rezolvare nerecursiva pentru problema P([]) ([] fiind lista vida)P([]) este: “Sa se afiseze elementele listei []” – rezolvarea este banala


Recursivitatea

struct nod{

int info;struct nod* urm;

} nod;

void afiseaza(struct nod* lista){

if (lista==NULL) return;printf(“%d ”, listainfo);afiseaza(listaurm);

}

Aici este rezolvarea problemei

afiseaza(NULL)


Recursivitatea

Sa presupunem ca avem o lista simplu inlantuita pe care dorim s-o afisam in ordine inversa (iterativ, rezolvarea nu mai este chiar atat de directa ca si in cazul afisarii normale)Problema apare sub forma P(L): “Sa se afiseze elementele listei L in ordine inversa”In cazul general, orice lista L este formata dintr-un prim element X urmat de o lista L’ (care contine cu un element mai putin decat L)Afisarea in ordine inversa a listei L presupune afisarea in ordine inversa a listei L’ dupa care trebuie afisat elementul X (primul element al listei L va aparea ultimul)Trebuie sa mai dam o rezolvare nerecursiva pentru problema P([]) ([] fiind lista vida)P([]) este: “Sa se afiseze elementele listei [] in ordine inversa” – rezolvarea este banala


Recursivitatea

struct nod{

int info;struct nod* urm;

} nod;

void afiseaza_invers(struct nod* lista){

if (lista==NULL) return;afiseaza_invers(listaurm);printf(“%d ”, listainfo);

}

Aici este rezolvarea problemei

afiseaza_invers(NULL)


Recursivitatea

Se poate observa usurinta cu care se pot exprima recursiv probleme care se rezolva, in mod normal, iterativAcest avantaj este compensat de faptul ca programele recursive consuma, de regula, mai multa memorie decat in varianta iterativa, deoarece la fiecare apel, parametrii de apel si eventualele variabile locale blocului apelat recursiv se copiaza din nou pe stivaSe poate usor imagina ce se intampla daca nu exista conditia de oprire a recursivitatii, adica acea rezolvare nerecursiva a problemei P(0)


Recursivitatea

Nu toate problemele se pot pune in forma P(N)Exista cazuri cand problema se poate pune in forma P(0) si rezolvarea problemei P(I) se va baza pe faptul ca problema P(I+1) este gata rezolvataIn acest caz, trebuie furnizata o rezolvare nerecursiva pentru problema P(N) unde N trebuie sa fie o valoare cunoscuta si pozitiva


Recursivitatea

Mai apoi, pot exista probleme recursive care depind de 2 sau mai multi parametriUn exemplu ar fi exprimarea recursiva a combinarilor de N luate cate K: C(N,K) = C(N-1,K)+C(N-1,K-1)

Pentru toate se poate aplica metoda prezentata, intr-o forma mai mult sau mai putin modificata si adaptata

recursivitatea

Documents