Ce este recursivitatea ?
Yüklə 117,02 Kb.
|
- Bu səhifədəki naviqasiya:
- Parametrii-valoare si parametrii-variabila
- Verificarea si simularea programelor recursive
- Tehnica eliminarii recursivitatii
- Exercitii
- (2) Reconstructia punctelor
- (6) Alcatuire chestionare
|
Ce este recursivitatea ? Un obiect sau un fenomen se defineste in mod recursiv daca in definitia sa exista o referire la el insusi. Recursivitatea este folosita cu multa eficienta in matematica. Spre exemplu, definitii matematice recursive sunt:
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). Recursivitatea e strins legata de iteratie.Iteratia este executia repetata a unei portiuni de program, pina la indeplinirea unei conditii (while, do-while , for din C). Recursivitatea presupune executia repetata a unui modul, insa in cursul executiei lui (si nu la sfirsit, ca in cazul iteratiei), se verifica o conditie a carei nesatisfacere, implica reluarea executiei modulului de la inceput, fara ca executia curenta sa se fi terminat. In momentul satisfacerii conditiei se revine in ordine inversa din lantul de apeluri, reluandu-se si incheindu-se apelurile suspendate. Un program recursiv poate fi exprimat: P=M(Si,P) , unde M este multimea ce contine instructiunile Si si pe P insusi. Structurile de program necesare si suficiente in exprimarea recursivitatii sunt functiile apelate prin nume. Recursivitatea poate fi directa - o functie P contine o referinta la ea insasi, sau indirecta - o functie P contine o referinta la o functie Q ce include o referinta la P. Apelul recursiv al unei functii trebuie sa fie conditionat de o decizie care sa impiedice apelul in cascada ( la infinit ); aceasta ar duce la o eroare de program - depasirea stivei. Exemplu generic:
Se pune intrebarea: "Ce este mai indicat de utilizat: recursivitatea sau iteratia?" Algoritmii recursivi sunt potriviti pentru a descrie probleme care utilizeaza formule recursive sau pentru prelucrarea structurilor de date definite recursiv ( liste, arbori ), fiind mai eleganti si mai simplu de inteles si verificat. Iteratia este uneori preferata din cauza vitezei mai mari si a memoriei mai reduse. Spre exemplu varianta recursiva a functiei Fibonacci duce la 15 apeluri pentru n=5, deci varianta iterativa este mult mai performanta. Parametrii-valoare si parametrii-variabila In C, cu imbunatatirile aduse de C++, exista doua tipuri de parametri formali: valoare si referinta. Apelul recursiv al unei functii face ca pentru toti parametrii-valoare sa se creeze copii locale apelului curent (in stiva) , acestea fiind referite si asupra lor facindu-se modificarile in timpul executiei curente a functiei. Cind executia functiei se termina, copiile sunt extrase din stiva, astfel incit modificarile operate asupra parametrilor-valoare nu afecteaza parametrii efectivi de apel, corespunzatori. De asemenea pentru toate variabilele locale se rezerva spatiu la fiecare apel recursiv. In cazul parametrilor referinta, pe stiva se depune adresa parametrilor actuali, astfel incat operarea se face direct asupra spatiului de memorie afectat parametrilor efectivi, de apel. Pe parcursul unui apel, sunt accesibile doar variabilele locale si parametrii pentru apelul respectiv, nu si cele pentru apelurile anterioare, chiar daca acestea poarta acelasi nume. De retinut: -pentru fiecare apel recursiv al unei functii se creaza copii locale ale parametrilor valoare si variabilelor locale, ceea ce poate duce la risipa de memorie; -orice parametru-variabila poate fi suprimat prin referirea directa in functie a variabilei ce figura ca parametru de apel. Verificarea si simularea programelor recursive Se face ca in cazul celor nerecursive, printr-o demonstratie formala, sau testind toate cazurile posibile. Se verifica intii daca toate cazurile particulare (ce se executa cind se indeplineste conditia de terminare a apelului recursiv) functioneaza corect. Se face apoi o verificare formala a functiei recursive, pentru restul cazurilor, presupunind ca toate componentele din codul functiei functioneaza corect. Verificarea e deci inductiva.Acesta e un avantaj al programelor recursive, ce permite demonstrarea corectitudinii lor simplu si clar. Exemplificare: Functia recursiva de calcul a factorialului:
Demonstrarea corectitudinii cuprinde doi pasi: -pentru n=1 valoarea 1 ce se atribuie factorialului este corecta -pentru n>1, presupunand corecta valoarea calculata pentru predecesorul lui n de catre fact(n-1), prin inmultirea acesteia cu n se obtine valoarea corecta a factorialului lui n. Tehnica eliminarii recursivitatii Orice program recursiv poate fi transformat in unul iterativ, dar algoritmul sau poate deveni mai complicat si mai greu de inteles. De multe ori, solutia unei probleme poate fi elaborata mult mai usor, mai clar si mai simplu de verificat, printr-un algoritm recursiv. Dar pentru implementare, poate fi necesara transformarea algoritmului recursiv in unul nerecursiv, in situatiile: -solutia problemei trebuie scrisa intr-un limbaj nerecursiv; un caz particular sunt compilatoarele ce "traduc" un program recursiv dintr-un limbaj de nivel inalt in cod masina (nerecursiv) -varianta recursiva ar duce la o viteza de executie si spatiu de memorie prea mari, transformarea in una nerecursiva, eliminind dezavantajele. Se va prezenta una din metodele de eliminare a recursivitatii ce foloseste o structura de date de tip stiva. In scrierea unei varianta nerecursive, trebuie parcursi toti pasii implicati in varianta recursiva, prin tehnici nerecursive. Recursivitatea implica folosirea a cel putin unei stive. La fiecare apel recursiv sunt depuse in stiva date, care sunt extrase la revenirea din acel apel. E simplu daca datele pentru un apel se organizeaza intr-o structura, un apel insemnind introducerea in stiva a unei structuri, revenirea, extragerea structurii. Se prezinta eliminarea recursivitatii pentru un program simplu, care citeste caracterele tastate pana la un blanc, tiparindu-le apoi in ordine inversa.
1.Algoritmi de traversare si inversare a unei structuri Traversarea si inversarea unei structuri inseamna efectuarea unor operatii oarecare asupra tuturor elementelor unei structuri in ordine directa, respectiv in ordine inversa. Desi mai uzuale sunt variantele iterative, caz in care inversarea echivaleaza cu doua traversari directe (o salvare in stiva urmata de parcurgerea stivei), variantele recursive sunt mai elegante si mai concise. Se pot aplica structurilor de tip tablou, lista, fisier si pot fi o solutie pentru diverse probleme (transformarea unui intreg dintr-o baza in alta, etc). Intr-o forma generala, algoritmii se pot scrie:
De observat importanta ca parametrul formal al celor doua functii sa fie de tip valoare, pentru a nu fi alterat de apelul recursiv. 2.Algoritmi care implementeaza definitii recursive O definitie recursiva e cea in care un obiect se defineste prin el insusi. Definitia contine o conditie de terminare, indicind modul de parasire a definitiei si o parte ce precizeaza definirea recursiva propriu-zisa. Ca exemple: algoritmul lui Euclid de aflare a c.m.m.d.c., factorialul, ridicarea la o putere intrega (prin inmultiri repetate), definirea recursiva a unei expresii aritmetice, curbele recursive, un mod de a privi permutarile, etc.
3.Algoritmi de divizare Tehnica divizarii ("divide and conquer"), fundamentala in elaborarea algoritmilor, consta in descompunerea unei probleme complexe in mai multe subprobleme a caror rezolvare e mai simpla si din solutiile carora se poate determina solutia problemei initiale (exemple: gasirea minimului si maximului valorilor elementelor unui tablou, cautarea binara, sortare Quicksort, turnurile din Hanoi). Un algoritm de divizare general s-ar putea scrie:
4.Algoritmi cu revenire (backtracking) Metoda se aplica problemelor in care solutia se poate reprezenta sub forma unui vector x=(x1,x2,...xn) c S=S1 x S2 x...x Sn, unde multimile Si sunt finite, S numindu-se spatiul solutiilor posibile. In particular, Si sunt identice avind acelasi numar M de elemente. Pentru fiecare problema concreta sunt date anumite relatii intre ucomponentele vectorului x, numite conditii interne. Determinarea tuturor solutiilor rezultat se poate face generind toate solutiile posibile si verificind apoi care satisfac conditiile interne. Dar timpul de calcul ar fi foarte mare (daca multimile Si ar avea numai cite 2 elemente, timpul ar fi proportional cu 2n). Metoda backtracking urmareste evitarea genararii tuturor solutiilor. Elementele vectorului x primesc valori pe rind, lui x1 i se atribuie valori, doar daca x1,x2,...,xi-1 au primit deja, valorile atribuite trebuind sa verifice conditiile de continuitate referitoare la x1,x2,...,xi. Doar apoi se trece la calculul lui xi+1. In cazul neindeplinirii conditiilor de continuitate, se alege urmatoarea valoare posibila pentru xi, daca Si a fost epuizat, se micsoreaza i, incercind o alta alegere pentru xi-1.
Pe acesta metoda se bazeaza rezolvarea unor probleme clasice ca: "opt regine", a "relatiilor stabile", colorarea unei harti, taierea unui fir de lungime l in parti de lungimi date, etc. O varianta a acestei metode este cea in care, pentru un xi c vector solutie , xi+1 poate fi ales dintr-un numar M de posibilitati:
Aceasta varianta se foloseste la rezolvarea problemelor: "saritura calului", iesirea dint-un labirint, etc. Se preteaza atunci cind pasul initial este definit si/sau numarul de pasi ai solutie nu este cunoscut. 5.Algoritmi "inlantuie si limiteaza" (Branch and Bound) Sunt inruditi cu cei backtracking, mai numindu-se si backtracking cu constrangeri.
(1) Labirint 3D Pentru problema de determinare a tuturor solutiilor de iesire dintr-un labirint 3D: sa se scrie un program pentru determinarea tuturor solutiilor si a optimului de iesire dintr-un labirint tridimensional. (2) Reconstructia punctelor Exista n puncte, p1, p2, ..., pn, toate localizate pe axa x, iar xi este coordonata lui pi. Se presupune ca x1=0 si punctele sunt numerotate de la stanga la dreapta. Aceste n puncte determina n*(n-1)/2 distante (de valori nu neaparat unice), d1, d2, ....,dm intre oricare 2 puncte distincte xi si xj. Problema reconstructie este urmatoarea: se dau m valori, (sortate in ordine crescatoare), care reprezinta setul de distante intre m=n*(n-1)/2 perechi de puncte. Se cere sa se reconstituie coordonatele celor n puncte. (3) Taieturi Sa se scrie un program care sa gaseasca toate variantele, precum si cea optima pentru taierea unui fir de lungime L in parti de lungimi L1,L2,...,Ln date, in conditiile: a)nu exista nici un fel de restrictie in ce priveste numarul de bucati din fiecare lungime b)se taie cel mult o bucata de fiecare lungime c)numarul de bucati de fiecare lungime sa difere prin cel mult o unitate (4) Formatare de text Se considera urmatoarea problema de formatare a textului unui paragraf, care este o secventa de n cuvinte, c1, c2, ..., cn, de lungimi a1, a2, ..., an, care trebuie afisate pe linii de lungime L. Cuvintele trebuie separate prin spatii, a caror lungime ideala este b, dar spatiile pot fi extinse sau comprimate (dupa comprimare trebuie sa ramina totusi > 0), astfel incat o linie ce contine cuvintele ci ci+1 ... cj sa ocupe exact lungimea L. Pentru fiecare spatiu b' care este este mai mare sau mai mic decat lungimea ideala b, se defineste un "gradul de uratenie" ca fiind |b' - b|. Pentru intregul paragraf, este de dorit ca suma acestor grade de uratenie sa fie minim. Se cere sa se scrie programul care determina valorile lungimilor spatiilor separatoare astfel incat sa se obtina o formatare cat mai estetica a textului. (5) Recursivitate Sa se scrie cite o functie recursiva pentru: a)transformarea unui intreg din baza 10 in alta baza data b)tiparirea nodurilor unei liste in ordine inversa c)analog cu b), dar pentru elementele unui tablou d)copierea in ordine inversa a liniilor dintr-un fisier text, in altul. (6) Alcatuire chestionare Se considera un set de N intrebari, fiecare avand un punctaj Pi. Sa se genereze toate chestionarele continand un numar de intrebari intre A si B si avand un punctaj total intre C si D. (7) Triunghi magic Se considera un triunghi format din n linii, pe fiecare linie i sunt i numere intregi pozitive, ca in exemplul de mai jos: 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 Sa se scrie un program care calculeaza cea mai mare suma a numerelor aflate pe un drum care leaga virful de sus al triunghiului cu baza. Drumul este astfel construit incat la fiecare pas se coboara pe diagonala, spre stinga sau spre dreapta. Exemplu: pentru triunghiul de mai sus, drumul cautat este: 7 - 3 - 8 - 7 - 5 (8) Labirint culori Se considera o suprafata caroiata de dimensiune n x n, in care fiecare patrat are una din culorile: galben, rosu, albastru sau verde. Configuratia suprafetei se citeste de la tastatura ( sau dintr-un fisier ). Sa se determine si sa se tipareasca daca exista drumuri ( minime ) intre colturile opuse - un drum trebuie sa cuprinda doar patrate de aceeasi culoare; deplasarea dintr-un patrat se poate face in oricare din cei opt vecini. (9) Cablaj Pe un circuit electric trebuie plasate n componente. Plasarea lor se face in n pozitii bine determinate, identificate cu numerele 1.. n. Se da o matrice c in care c[i,j] reprezinta numarul de conexiuni care trebuie facute intre componentele i si j, precum si o matrice d, cu d[p,q] reprezentind distanta intre punctele p si q. Cablarea consta in plasarea fiecarei componente intr-o anumita pozitie. Nu se pot aseza 2 componente in aceeasi pozitie. Costul cablarii este suma valorilor c[i,j]*d[p,q], unde componenta i a fost plasata in pozitia p iar componenta j in pozitia q. Se cere sa se determine o plasare a componentelor pe pozitii astfel incit costul total al cablarii sa fie minim. Fisierul de intrare, cu numele citit de la tastatura, contine: - pe prima linie valoarea lui n - pe urmatoarele n linii elementele liniilor lui C - pe urmatoarele n linii elementele liniilor lui D Iesirea va consta in afisarea permutarii care duce la costul minim, in forma: pozitia 1 - componenta x; pozitia 2 - componenta y ...... Yüklə 117,02 Kb. Dostları ilə paylaş:
|