informatica recursivitate aplicata

Colegiul National "Ienachita Vacarescu"

 

CUPRINS:

Argument

Capitolul 1 Prezentarea teoretica a Recursivitatii

Capitolul 2 Reguli pentru construirea unui program recursiv

Capitolul 3 Aplicatii cu subprograme recursive si prezentarea acestora

Algoritmul pentru determinarea valorii minime/maxime

Calculul celui mai mare divizor comun a doua numere

Divizorii unui numar

Conversia in baze de numeratie

Calculul factorialului n!

Capitolul 4 Variabile locale

Capitolul 5 Probleme propuse

Problema 1. (sursa recursiva, sursa iterativa, avantajele si dezavantejele fiecarei implementari)

Problema 2. (sursa recursiva, sursa iterativa, avantajele si dezavantejele fiecarei implementari)

Problema 3. (sursa recursiva, sursa iterativa, avantajele si dezavantejele fiecarei implementari)

Problema 4. (sursa recursiva, sursa iterativa, avantajele si dezavantejele fiecarei implementari)

Problema 5. (sursa recursiva, sursa iterativa, avantajele si dezavantejele fiecarei implementari)

Bibliografie

Argument

Am ales acest capitol din programare deoarece este cel mai clar, concis, rapid, usor de inteles si verificat. Variantele recursive ale problemelor sunt mult mai clare si mai usor de implementat fata de variantele iterative.

Recursivitatea este folosita cu multa eficienta in matematica. Spre exemplu, definitii matematice recursive sunt: definitia numerelor naturale, definitia functiei factorial definitia functiei Ackermann definitia functiei Fibonacci

Utilitatea practica a recursivitatii rezulta din posibilitatea de a defini un set infinit de obiecte printr-o singura relatie sau printr-un set finit de relatii.

Recursivitatea s-a impus in programare, odata cu aparitia unor limbaje de nivel inalt, ce permit scrierea de module ce se autoapeleaza (PASCAL, LISP, ADA, ALGOL, C sunt limbaje recursive, spre deosebire de FORTRAN, BASIC, COBOL, nerecursive).

Capitolul 1: RECURSIVITATEA

Recursivitatea reprezinta o tehnica de programare de o importanta deosebita. Notiunea de recursivitate din programare este derivata in mod natural din notiunea matematica.

În matematica, o notiune este definita recursiv daca in cadrul definitiei apare insasi notiunea care se defineste.

În programare, recursivitatea este exprimata cu ajutorul subprogramelor, deoarece ele se identifica printr-un nume care este specificat apoi in apeluri.

Un subprogram este recursiv daca apelul sau apare cand subprogramul este activ.

Daca apelul apare in instructiunea compusa a subprogramului, recursivitatea se numeste directa.

Daca apelul apare in instructiunea compusa a unui alt subprogram care se apeleaza din primul subprogram, recursivitatea se numeste indirecta.

Activarea unui subprogram recursiv presupune la fel ca in cazul unuia nerecursiv, alocarea pe stiva (STACK) a variabilelor locale, a parametrilor si a adresei de revenire. Datorita acestui fapt, o solutie recursiva este eficienta numai daca adancimea recursivitatii (nr. de auto-apeluri) nu este foarte mare.

Stiva este o succesiune ordonata de elemente, delimitata prin doua capete, in care adaugarea si eliminarea elementelor se poate face pe la un singur capat, numit varful stivei. O stiva care nu contine nici un element stiva vida. În orice moment, putem scoate din stiva numai elementul care a fost introdus ultimul, motiv pentru care vom spune ca stiva functioneaza dupa principiul LIFO (Last In First Out - "Ultimul Intrat Primul Iesit")

Recursivitatea are avantajul ca reduce drastic lungimea textului sursa al unui program. De aceea solutiile recursive sunt mai clare. Recursivitatea reprezinta o solutie avantajoasa in cazul problemelor complexe care se rezolva prin backtracking, in acelea ale caror date sunt definite recursiv sau in problemele ale caror solutii pot fi definite in termeni recursivi.

Utilizarea tehnicilor recursive nu conduce, insa, intotdeauna la solutii optime, fiind recomandata analiza eficientei solutiei mai avantajoase in cazul dat. De multe ori trebuie avut in vedere ca recursivitatea, mai ales cea indirecta poate genera dificultati deosebite in depanarea programelor.

Spre deosebire de alte limbaje mai vechi (de exemplu Fortran), limbajul C++ rezolva apelurile recursive prin chiar mecanismul apelului subprogramelor. Esential este faptul ca la punerea in executie a unui subprogram, se aloca spatiu pentru parametrii, valoare si variabilele locale si se intializeaza parametrii valoare, in conformitate cu valorile parametrilor efectivi.

Proiectarea oricarui program recursiv trebuie sa asigure iesirea din recursivitate. De aceea, apelul recursiv este intotdeauna conditionat.

Mecanismul recursivitatii ne aminteste de cunoscutele si originalele papusi Matruska, punerea sa in executie fiind similara deschiderii succesive, urmata de inchiderea lor in ordine inversa.

Capitolul 2: REGULI PENTRU CONSTRUIREA UNUI PROGRAM RECURSIV

Corpul unui subprogram recursiv descrie algoritmul folosind doua elemente:

è     Cazul general al soluriei. Contine toate prelucrarile necesare pentru a reduce dimensiunea problemei in vederea apropierii de rezultatul final. Cea mai importanta operatie care se executa este autoapelul.

è     Cazul de baza al solutiei. Contine e operatie care rezolva un caz special al problemei, fara a se folosi autoapelul.

Recursivitatea este un proces repetitiv si este obligatoriu sa existe o conditie de oprire a repetitiei. Cele doua cazuri se combina folosind o structura alternativa if else. Conditia de oprire a recursivitatii este exprimata printr-o expresie logica ce trebuie sa depinda de parametrii subprogramului sau de variabilele sale locale.

Orice definitie recursiva trebuie sa asigure conditia de consistenta, adica valoarea functiei trebuie sa fie direct calculabila sau calculabila cu ajutorul unei valori direct calculable. Aceasta inseamna ca modificarea parametriior si/sau a variabilelor locale, de la o activare la alta, trebuie sa asigure conditia de iesire din recursivitate.

Capitolul 3: APLICATII CU SUBPROGRAME RECURSIVE SI PREZENTAREA ACESTORA

Algoritmul pentru derminarea valorii minime/maxime

Pentru calculul valorii minime dintr-un sir de n numere citite de la tastaturs, se vor folosi functiile min() si max() care au fost definite recursive.

# include <iostream.h>

int max (int a, int b)

int min (int a, int b)

void main ()

cout<<"maxim= "<<x<<endl<<"minim= "<<y;

Calculul celui mai mare divizor comun a doua numere

Un alt algoritm elementar pe care il putem implementa foloind recursivitatea este calculul celui mai mare divizor comun dintre doua numere naturale a si b. Valorile lui a si b se introduc de latastatura.

Varianta 1. Solutia recursiva se bazeaza pe algoritmul lui Euclid (conditta b!=0)

1. Se imparte a la b si se obtine restul r (r= a mod b)

2. Se executa operatiile de atribire a=b; b=r.

3. Daca b!=0 atunci se revine la pasul 1, adica se reia executa functiei atriuindu-se parametrilor de intrare urmatoarele valori: parametrul a valoarea b, iar parametrului b valoarea a mod b. Daca b=0, atunci cmmdc=a.

#include <iostream.h>

int cmmdc (int a, int b)

void main()

Varianta 2. Solutia recursiva se bazeaza pe   algoritmul prin scaderi repetate (conditia a! b)

Se scade, din numarul mai mare, celalalt numar: daca a >b, se executa operatia de atribuire a a-b iar daca se   b>a se executa operatia de atribuire b=b-a.

Daca a!=b, atunci se revine la pasul 1 adica se reia executia functiei atribuindu-se parametrilor de intrare urmatoarele valori: daca a>b, parametrului a i se atribuie valoarea a-b, iar daca b>a parametrului b I se atribuie valoarea b-a si in ambele cazuri, celalalt parametru ramane neschimat.

Daca a=b, atunci cmmdc=a.

#include<iostream.h>

int cmmdc (int a, int b)

void main ()

Divizorii unui numar

Exemplul 1. Afisarea divizorilor unui numar. Se genereaza divizorii posibili (d) ai numarului n, pornind de la valoarea 1. Daca divizorul posibil este mai mic decat n/2, se verifica daca numarul n este divizibil prin el. Daca este divizibil, se afiseaza divizorul d. Se reia apoi executia functiei, pentru urmatorul divizor posibil. Se va evalua functia divizor (n,1).

#include<iostream.h>

void divizor (int n, int d)

void main ()

Sau

#include<iostream.h>

void divizor (int n, int d)

void main ()

Exemplul 2: Sa se descompuna un numar in factori primi. Se genereaza factorii primi posibili (f) ai numarului n, pornind de la valoarea 2 a factorului, pana cand se elimina din numar toti factorii primi (n=1). Se foloseste parametrul p pentru a calcula exponentul factorului prim. Daca f este factor prim, se apeleaza functia pentru numarul din care s-a eliminat un factor prim (n/f) si pentru valoarea exponentului p incrementata cu 1. Daca f nu este factor prim in numarul n obtinut, se verifica daca a fost prim (p !=0)-caz in care se afiseaza factorul prim (f) si exponentul (p) - dupa care se apeleaza functia pentru urmatorul factor prim posibil (f+1) cu exponentul 0. Daca s-au eliminat din numar toti factorii primi, se verifica daca ultimul factor a fost prim (p!=0) - caz in care se afiseaza factorul prim (f) cu exponentul (p). Se va evalua functia factor (n,2,0).

#include<iostream.h>

void factor (int n, int f, int p)

else if (p!=0) cout<<f<<"la puterea"<<p;}

void main ()

Conversia in baze de numeratie

Se converteste un numar n scris in baza 10 intr-un numar scris in baza q (1<q<10). Daca n<q, inseamna ca numaarul este reprezentat deja in baza q, deoarece se folosesc acelasi cifre pentru reprezentarea lui. În cazul in care n>=q algoritmul de conversie este:

atribuirea catului valoarea numarului c=n

se calculeaza restul impartirii numarului la valoarea q (r= n mod q) - o cifra a numarului - si se afiseaza (primul rest este cifra cea mai putin semnificativa)

se evalueaza c - catul impartirii numarului la q. Daca c>=q, se revine la pasul 2, adica se reia executia subprogramului, atribuind parametrului de intrare valoarea n div q. Daca c<q, se termina procesul repetitiv si catul obtinut va fi ultima cifra (cea mai semnificativa)

Tiparirea cifrelor obtinute se face in ordinea inversa a extragerii (la fel ca si in cazul functiei recursive, prin care se afisa inversul unui sir de caractere). Înseamna ca, la fiecare apel al functiei, cifra obtinuta prin calcularea restului se va pastra de fiecare data in cate o imagine a variabilei de memorie folosita in functia recursiva - variabila cifra. Tiparirea cifrelor se va face in ordinea inversa a obtinerii lor, deoarece prima cifra care se va tiparii va fi cea corespunzatoare ultimului apel, iar ultima cifra care se va tipari va fi cea corespunzatoare primului apel:

#include<iostream.h>

void conversie (int n, int q)

void main ()

Calculul factorialului n!

Apelul factorialului se termina cand n == 0. Un apel fact(n) cauzeaza exact n apeluri ale functiei factorial.

#include<iostream.h>

unsigned long fact(int n)

void main()

Capitolul 4: VARIABILELE LOCALE

O variabila locala a unui subprogram este definita in interiorul subprogramului si poate fi folosita numai in cadrul sau. În cazul subprogramelor recursive, fiecare autoapel al subprogramului inseamna un nou proces, caruia i se rezerva o noua zona de memorie interna in care sa se execute. Implicit, inseamna si o noua definire a variabilei locale, adica o noua zona de memorie interna alocata pentru variabila locala, numai pentru acel apel al subprogramului.

Asadar, variabila locala este unica pentru un apel al subprogramului. Daca subprogramul este apelat recursiv de n ori, vor exista n imagini ale aceleiasi variabile locale, cate una pentru fiecare apel. Fiecare imagine va avea un continut diferit, corespunzator apeiului.

La activarea fiecarui subprogram recursiv, varful stivei sistemului urca, si se salveaza in stiva instanta subprogramului apelant. În acest mod, in stiva se vor regasi toate instantele activarii subprogramului recursiv. Înainte de a se reveni dintr-o activare a unui subprogram recursiv, varful stivei coboara si este adus la valoarea anterioara activarii.

Capitolul 5: PROBLEME PROPUSE

5.1 Problema 1.

Sa se genereze toate numerele binare cu n cifre care au m cifre de 0 si restul cifrelor 1. Valorile pentru n si m se citesc de la tastatura. Combinatiile posibile de m cifre de 0 si n-m cifre de 1 se vor genera recursiv. Din multimea de combinatii posibile se vor alege numai acelea care pot forma un numar cu n cifre.

Rezolvarea problemei

Sursa recursiva

#include<iostream.h>

int n,m,v[101];

void numar(int poz, int nrzero)

v[poz]=1; //cifra poate fi 1 oricand

numar(poz+1, nrzero);

}

else if(nrzero==m) //afisez numarul numai daca are m zerouri

void main()

Sursa iterativa

#include<iostream.h>

int v[50],n,m;

unsigned long min,max;

void afisare() // functia afiseaza elementele din vector

void test() /* functia test, testeaza daca numarul convine cerintelor date din problema, adica daca in numar se afla m cifre de 0; daca da sunt afisate cu ajutorul functiei anterioare */

void doi_zece(unsigned long &x) /* functia transforma numerele din vector din baza 2 in baza 10 */

void zece_doi(unsigned long x) /* functia transforma numerele din vector din baza zece in baza 2 */

test();

void main()

Avantajele si dezavantajele fiecarei implementari

Avantaje

Varianta recursiva este mai clara si mai usor de implementat.

În general varianta iterativa este mai rapida dar in cazul acestei probleme rapiditatea programelor depinde de valorile date.

Executia algoritmului iterativ se face intr-o singura etapa, care consta in rezolvarea problemei pornind de la o valoare initiala cunoscuta, pana la obtinerea valorii finale(valoarea ceruta), adica 'de jos in sus'.

Dezavantaje

Executia algoritmului recursiv se face in 2 etape: in prima etapa se descompune problema, pornind de la valoarea ceruta pana la valoarea initiala, cunoscuta, adica 'de sus in jos', iar in a doua, se revolva problema pornind de la valoarea initiala cunoscuta pana la obtinerea valorii cerute, adica 'de jos in sus".

5.2 Problema 2

Sa se genereze toate submultimile multimii . Multimile generate sunt A_k = , cu i care poate lua valori de la 1 la n, si a_k1<a_k2<a_k3< .. <a_ki. De exemplu, pentru n=3 submultimile sunt: , , , , , si .

Rezolvarea problemei

Sursa iterativa:

#include<iostream.h>

void init (int c[100], int n)  /* definirea subprogramului init cu parametrii formali: vectorul cu elementele multimii si numarul de elemente */

void submult (int c[100], int b) /* definesc subprogramul submult pentru afisarea submultimilor cu parametrii formali vectorul c in care avem elementele multimii si b, numarul de elemente */

if (i==0) ok=0;

else

}

void main () //intru in main pentru a afisa valorile pe ecran

Sursa recursiva:

#include <iostream.h>

void rec(int i,int c[],int n) /* definesc subprogramul rec cu parametrii formali i pentru pozitie, vectorul c si numarul de elemente n; pe care il voi folosi la afisarea submultimilor */

void init (int c[], int n) /* declarez functia init cu parametrii formali c, vectorul care il voi initializa cu 0 si numarul de elemente n; care o voi folosi la initializarea vectorului c cu 0 */

void submult (int c[], int n) /*declarez functia submult cu parametrii formali c, vectorul folosit la generarea submultimilor si numarul de elemente n; pentru generarea submultimilor */

if (i==0) ok=0;

else

}

void main()  /* intru in main pentru a citi n-ul, pentru a apela functiile si pentru a afisa */

Avantaje si dezavantaje

Rezolvarea problemei cu ajutorul metodei recursive este mai scurta, mai usor de urmarit. Este mai clara drept pentru care poate fi inteleasa mai usor. În unele cazuri este necesara datorita faptului ca sunt lucruri ce pot fi realizate numai prin intermediul recursivitatii, exemplu ar fi adancimea recursivitatii. Un dezavantaj este timpul de executie deoarece creste cu cat adancimea este mai mare a recursivitatii, din cauza timpilor necesari pentru mecanismul de apel si pentru administrarea stivei de sistem.

5.3 Problema 3.

Scrieti un program care sa afiseze termenul n din urmatoarele siruri, cu a₀=b₀=1:

a_n=a_n-1+b_n-1;

b_n=a_n-1-b_n-1;

Calculati adancimea recursivitatii pentru apelurile a(n) si b(n).

Tabelul de evolutie a sirurilor a_n si b_n:

Varianta I de rezolvare a problemei:

Sursa iterativa:

#include<iostream.h>

main()

Sursa recursiva:

#include<iostream.h>

int q; //variabila globala ce calculeaza adancimea recursivitatii

int sir (int n) //functia ce calculeaza al n-lea termen din sirul an

void main ()

Varianta a II-a de rezolvare a problemei:

Sursa iterativa:

#include<iostream.h>

void main( )

cout<< ac<<" "<<bc<<endl /*la iesirea din for se vor afisa ultimele valori calculate ale lui a si b*/

}

}

Sursa recursiva:

#include<iostream.h>
int n,q;
void generare(long &a,long &b,int k) /*am transmis a si b prin referinta, deoarece vrem sa se retina ultimele valori ale acestora*/

void main( )

Avantajele si dezantajele implementarilor:

În ambele variante de rezolvare metodele recursive sunt mai lente; variantele iterative sunt mai rapide datorita faptului ca nu mai realizeaza depunerea si intoarcerea in stiva.

Totusi, variantele recursive sunt mai clare si mai usor de implementat.

5.4 Problema 4

Sa se verifice daca un numar n este superprim. Un numar este superprim daca toate prefixele sale sunt numere superprime (de exemplu, numarul 171 este superprim, deoarece toate prefixele sale - 1, 17, 171 - sunt numere prime). Vor fi implementate recursiv atat subprogramul care testeaza daca un numar este prim, cat si subprogramul care extrage toate prefixele numarului.

Rezolvarea problemei:

Sursa recursiva:

#include<iostream.h>

#include<conio.h>

int x;

int prim(int i,int x) // subprogramul verifica daca un numar este prim

int superprim(int x) /* un numar este superprim daca prefixele sale sunt numere prime, astfel acest subprogram verifica daca prefixul numarului adica numarul div 10 este tot un numar prim */

void main()

Sursa iterativa:

#include<iostream.h>

#include<conio.h>

int x;

int prim(int x)  //subprogramul verifica daca un numar este prim

int superprim(int x) /* un numar este superprim daca prefixele sale sunt numere prime, astfel acest subprogram verifica daca prefixul numarului adica numarul div 10 este tot un numar prim */

return ok;}

void main()

Avantaje si dezavantaje

Rezolvarea problemei cu ajutorul metodei recursive este mai scurta, mai usor de urmarit. Este mai clara drept pentru care poate fi inteleasa mai usor.

5.5 Problema 5

Scrieti un subprogram care sa calculeze valoarea unui polinom de gradul n, cu coeficienti intregi, intr-un punct real x.Gradul polinomului, coeficientii lui si valoarea lui x se citesc de la tastatura.

Rezolvarea problemei:

Sursa iterativa:

#include<iostream.h>

void main ()

//cer coeficientul lui x

for(i=0;i<=n;i++) //parcurg vectorul element cu element

cout<<rez; //afisez rezultatul

Sursa recursiva:

#include<iostream.h>

#include<math.h>> /* folosesc si biblioteca math.h pentru ca folosesc functia pow pentru a ridica la putere */

float rez=0; //initializez variabila rez in care se va salva rezultatul cu 0

float polinom(int n,int x,int a[100]) /*functia polinom care calculeaza valoarea unui polinom cu parametrii n(lungimea vectorului a),x(numarul real),vectorul a(contine coeficientii acestui polinom) */

void main ( )

rez=polinom(n,x,V /*apelez functia polinom cu parametrii sai si salvez rezultatul in variabila reala rez */

cout<<rez; //afisez rezultatul

Avantajele si dezavantajele fiecarei implementari

Varianta iterativa este mai rapida decat cea recursiva. În schimb varianta recursiva este mai clara, mai usor de citit, si mult mai scurta.

Bibliografie

Informatica, manual pentru clasa a XI-a

Mariana Milosescu

Editura Didactica si pedagogica, 2006

Informatica, manual pentru clasa a X-a

D. Fanache, N. Istrate, M. Duta

Editura Gimnasium, 2000

https://www.timsoft.ro/aux/module/modul11.html