Recursivitate1. Noiunea de algoritm recursiv Un algoritm recursiv se caracterizeaz prin proprietatea c se auto-apeleaza, adic din interiorul lui se apeleaz pe el nsui. Din afara algoritmului facem un prim apel al acestuia, dup care algoritmul se auto-apeleaza de un anumit numr de ori: la fiecare nou auto-apelare a algoritmului, se execut din nou secvena de instruciuni ce reprezint corpul su, eventual cu alte date, crendu-se un aa-numit lan de auto-apeuri recursive. Intuitiv, putem spune c un algoritm recursiv are acelai efect ca i un ciclu: repet execuia unei anumite secvene de instruciuni. Dar, la fel ca n cazul unui ciclu, este necesar ca repetarea s nu aiba loc la infinit. De aceea, n corpul algoritmului trebuie s existe cel puin o testare a unei condiii de oprire, la ndeplinirea creia se ntrerupe lanul de auto-apeluri. Majoritatea algoritmilor repetitivi se pot implementa att in variant nerecursiv (care se mai numete si iterativ), folosind cicluri, ct i n variant recursiv. Rmne n sarcina programatorului s aleag ntre implementarea iterativ i cea recursiv, cntarind avantajele i dezavantajele fiecreia, de la caz la caz. Varianta recursiv este recomandat n special pentru problemele definite prin relaii de recuren, care permit o formulare a rezultatelor mult mai clar i mai concis. Pe de alt parte, funcionarea algoritmilor recursivi este n general mai greu de urmrit, i, n plus, acetia necesit un timp de execuie mai lung i un spaiu de memorie mai mare. Extinznd definiia, vom numi funcie recursiv, o funcie care din corpul ei se apeleaz pe ea nsi. Dar orice funcie recursiv trebuie s ndeplineasc dou cerine: s se poat executa cel puin o dat fr a se auto-apela; toate auto-apelurile s se produc astfel ncat s se tind spre ndeplinirea condiiei de execuie fr auto-apelare. 2. Exemple de algoritmi recurisivi. Relaii de recuren iruri definite prin relaii de recuren Un ir a1, a2 , ... ,an , ... este o succesiune de valori numite elementele irului, aranjate ntr-o ordine bine definit. Fiecare element ocup n cadrul irului o poziie fixat, care se numete rangul elementului. Unele iruri pot fi definite cu ajutorul unor formule care exprim orice termen al irului, ncepnd cu un anumit rang, n funcie de termenul precedent sau n funcie de termenii precedeni. O astfel de formul se numete relaie de recurena. Pentru a putea defini recurent un ir, mai trebuie sa indicm primul termen sau primii termeni. irul lui Fibonacci: este un ir de numere ntregi ( F1 ,F2 , ..., Fn ,...), definit recurent astfel: primii doi termeni sunt egali cu 1, apoi, fiecare termen ncepnd cu al treilea, este egal cu suma dintre precedentul si anteprecedentul su. Pentru un termen oarecare Fk (termenul de rang k), precedentul sau este Fk-1 (de rang k-1), iar antecedentul su este Fk-2 (de rang k-2). Astfel, F1=1, F2=1 i Fk=Fk-1+Fk-2 k 3. De exemplu: F3=F2+F1=1+1=2 (pentru k=3), F4=F3+F2=2+1=3 (pentru k=4), F5=F4+F3=3+2=5 (pentru k=5), etc. Se obine irul 1, 1, 2, 3, 5, 8, 13, 21, 34,... Pentru o descriere complet scriem o relaie de recuren 1, pentru k = 1 i 2 Fk = care nglobeaz att formula de calcul, ct i valorile termenilor Fk 1 + Fk 2 , pentru k 3 definii separat: Caracterul recursiv al algoritmului pentru determinarea termenilor irului lui Fibonacci este evident. Pentru a calcula un termen oarecare Fk , avem nevoie de termenii precedeni Fk-1 i Fk-2. Dar aflarea termenilor Fk-1 i Fk-2 se poate face cu acelai algoritm, doar c n loc de k avem k-1 respectiv k-2. Prin urmare, algoritmul care calculeaz termenul Fk trebuie s se auto-apeleze de dou ori, n scopul determinrii termenilor Fk-1 i Fk-2. 1

3. Relaii de recuren pentru expresii matematice Nu numai pentru iruri putem defini relaii de recuren, ci si pentru expresii matematice. Factorialul unui numr natural. Factorialul unui numr natural k este k!=123...(k-1)k (produsul numerelor naturale pn la k), care se mai poate scrie k!=k(k-1)...321. Dar (k-1)...321 este tocmai (k-1) ! (produsul numerelor naturale pn la k-1). De aici se deduce o aa numit relaie de recuren: k!=k(k-1) ! . Observm ns c factorialul lui 0 nu se poate calcula cu relaia anterioar, acesta fiind un caz care trebuie tratat separat. Folosind faptul c 0!=1 (definit matematic), obinem relaia de recurena complet: 1 , pentru k = 0 k!= k (k-1 )!, pentru k > 0 Caracterul recursiv const n faptul c din corpul algoritmului care calculeaz k! se auto-apeleaz algoritmul pentru a calcula (k-1)!.

Suma cu n termeni: suma printre n numere naturale impare De exemplu pentru n=5, irul primelor cinci numere naturale impare este(1, 3, 5, 7, 9), iar suma acestora este S5=1+3+5+7+9. Observm c se poate stabili o coresponden ntre rangul unui termen i valoarea sa. Astfel: primul termen, cu rangul 1, este 1, care se mai poate scrie 2*1-1; al doilea termen, cu rangul 2, este 3, care se mai poate scrie 2*2-1;...................................................................................................................... ultimul termen, cu rangul n=5, este 9, adic 2*5-1, adic 2*n-1.

Pe caz general, irul primelor n numere naturale impare este (1, 3, 5,.., 2n-1). Notnd termenii irului cu a1, a2, ..., an , observm c un termen oarecare ak (de rang k) are valoarea 2*k-1. Vom spune c irul de mai sus este definit prin formula termenului general ak=2*k-1. Suma primelor n elemente naturale este Sn=a1+a2+...+an=1+3+5+...+2n-1. Dac al n-lea termen, cel de rang n, este 2*n-1, atunci al (n-1)-ulea termen este 2(n-1)-1, adic 2*n-3 (pur i simplu am nlocuit pe n cu n-1). Astfel, Sn=1+3+5+...+(2*n-3)+(2*n-1). Dar 1+3+5+... +(2*n-3) reprezint suma primelor n-1 numere naturale impare notata Sn-1, deci Sn = (2n-1)+ Sn-1 . Pentru n=0, avem cazul particular S0=0. Obinem astfel relaia de recuren complet : Sn= (2n-1 ) + S0, pentru n = 0 n 1 , pentru n > 0

i aceast relaie genereaz un algoritm recursiv: pentru a calcula suma Sn, avem nevoie de suma Sn-1. Aplicaii: 1.Deducei formula termenului general pentru irurile de mai jos: 1 2 3 4 a) 2, 4, 8, 16, ... b) 1, 5, 9, 13, ... c) , , , , ... d)* 0, 1, 1, 3, 7, 17, 41 ... 2 3 4 5 2. deducei o relaie de recuren care s defineasc urmtoarele expresii: a) produsul primelor n numere naturale pare p=2*4*6*.....*(2n); b) suma primelor n numere naturale S=1+2+3+...+n; c) expresia E=1+4+7+...+(3n-2); d) expresia F=3*7*11*...... *(4n-1). 3. Deducei termenii urmtoarelor iruri definite prin relaii de recuren: a) an+1=1+a 2 ( ) n 1, a0=1 n b) xn=2* xn-1+xn-2 ( ) n 2, x0=0, x1=1 2

4. Rolul stivei in executarea subprogramelor recursive Stiva este o succesiune ordonata de elemente, delimitate prin doua capete, in care adaugarea si eliminarea elementelor se poate face pe la un singur capat, numit varful stivei. In orice moment putem scoate din stiva doar elemental care a fost introdus ultimul, motiv pentru care spunem ca stiva functioneaza dupa principiul LIFO(Last In First Out, in traducere Ultimul intrat primul iesit). Altfel spus, extragerea valorilor din stiva se face in ordine inversa introducerii lor. Limbajul C++ dispune de propria sa stiva, numita stiva interna, gestionata de catre compilator, care ocupa o parte din memoria interna rezervata programului. Orice functie foloseste aceasta stiva atunci cand se executa. In momentul in care o functie P apeleaza o functie S, se salveaza automat pe stiva interna adresa de revenire si contextual modulului apelant P( care cuprinde totalitatea variabilelor locale si a parametrilor transmisi prin valoare). Odata cu inchiderea executiei modulului apelat S, se revine in P, restaurandu-se valorile salvate pe stiva interna. In cazul unei functii recursive (care este atat modulul apelant cat si modulul apelat), acest mecanism al stivei este de foarte mare importanta: atunci cand se executa un lant de auto-apeluri recursive, la fiecare auto-apel variabilele locale si parametri functiei recursive se salveaza pe stiva, iar la revenirea in ordine inversa din lant aceste valori se restaureaza de pe stiva. 5. Functii recursive Functii recursive care returneaza o valoare Aplicatie rezolvat: Calculul factorialului unui numar natural. Fiind dat un numar natural n, sa se afiseze n!, folosind o functie recursiva. Reamintim : n!= 1 * 2 *.*n. De exemplu, 4!= 1*2*3*4=24 Algoritmul in varianta ne-recursiva Valoarea lui n!, se calculeaza ca un produs in variabila p. Initializam p cu 1. Intr-un ciclu, in variabila k parcurgem pe rand toate numerele naturale de la 1 la n (valoarea initiala a contorului este k=1, ciclul se executa cat timp k> n; p=1; for(k=1; k0) cout0) { ex(k-1); 2. Formulati o fraza care sa descrie actiunea functiei recursive ex. cout0? 2>0? da => se salveaza pe stiva 2 si are loc auto-apelul ex(1) Auto-apelul ex(1): k 1; k>0? 1>0? da => se salveaza pe stiva 1 si are loc auto-apelul ex(0) Auto-apelul ex(0): k 0; k>0? 0>0? nu => in acest moment s-a incheiat lantul de auto-apeluri pe care il reamintim: functia mainex(3) ex(2) ex(1) ex(0) Urmeaza lantul de reveniri, in ordine inversa: ex(0) ex(1) ex(2) ex(3) functia main Asadar, pentru n=3 au fost aslvate pe stiva valorile 3,2,1, in aceasta ordine. In 1 lantul revenirii, se Prg.princ ex(3) ex(2) ex(1) ex(0) 2 2 restaureaza si se tiparesc 3 3 3 valorile respective in ordinea inversa salvarii, respectiv 1,2,3. restaureaza restaureaza restaureaza Raspuns corect: e)k=3 afiseaza 3 k=2 afiseaza 2 k=1 afiseaza 1

2) Pe caz general, programul afiseaza primele n numere naturale 1,2,3,...,n in aceasta ordine. 6