Relatii de recurenta
Siruri definite prin relatii de recurenta:
Def:Un sir a1,a2,...an este o succesiune de valori numite elementele sirului,aranjate intr-o ordine bine definita.Fiecare element ocupa in cadrul sirului o pozitie fixata,care se numeste rangul elementului.
Unele siruri pot fi definite cu ajutorul unor fomule care exprima orice termen al sirului,incepand cu un anumit rang,in functie de termenul precedent sau in functie de termenii precendenti.O astfel de formula se numeste relatie de recurenta.Pentru a putea defini recurent un sir,mai trebuie sa indicam primul termen sau primii termeni
Sirul lui Fibonacci:
Sirul lui Fibonacci este un sir de numere intregi(F1,F2,…Fn),definit recurent astfel:primii doi termeni sunt egali cu 1,apoi,fiecare termen incepand cu al treilea,este egal cu suma ditre precedentul si anteprecedentul sau.
Pentru un termen oarecare Fk(termenul de rang k),precedentul sau este Fk-1(de rang k-1),iar anteprecedentul sau este Fk-2(de rang k-2).Astfel,F1=1,F2=1 si Fk=Fk-1+Fk-2, v k>=3.
De exemplu:F3=F2+F1=1+1=2(pentru k=3),F4=F3+F2=2+1=3(pentru k=4)etc.
Se obtine sirul 1,1,2,3,5,8,13,21,34,…
Pentru o descriere completa scriem o relatie de recurenta care inglobeaza atat formula de calcul,cat si valorile termenilor definiti separat:
F1={1,pt k=1 si 2;Fk-1+Fk-2,pt k>=3}
Caracterul recursiv al algoritmului pentru determinarea termenilor sirului lui Fibonacci este evident.Pentru a calcula un termen oarecare Fk,avem nevoie de termenii precedenti Fk-1 si Fk-2.Aflarea termenilor Fk-1 si Fk-2 se poate face cu acelasi algoritm,doar ca in loc de k avem k-1 respectiv k-2.Prin urmare,algoritmul care calculeaza termenul Fk trebuie sa se auto-apeleze de doua ori,in scopul determinarii termenilor Fk-1 si Fk-2.
Relatii de recurenta pentru expresii matematice:
Nu numai pentru siruri putem defini relatii de recurenta,ci si pentru expesii matemaice,asa cum vom vedea in exemplele urmatoare.
Factorialul unui numar natural
Factorialul unui numar natural k este k!=1*2*3*..*(k-1)*k(produsul numerelor naturale pana la k),care se mai poate scrie k!=k*(k-1)*…*3*2*1.Dar (k-1)*…*3*2*1 este tocmai (k-1)!.De aici se deduce o asa numita relatie de recurenta:k!=k*(k-1)!.Observam insa ca factorialul lui 0 nu se poate calcula cu relatia anterioara acesta fiind un caz care trebuie tratat separat.Folosind faptul ca 0!=1(definit matematic),obtinem relatia de recurenta completa:
K!={1,pt k=0;k*(k-1)!,pt k>0)
Caracterul recursiv consta in faptul ca din corpul algoritmului care calculeaza k! se auto-apeleaza algoritmul pentru a calcula (k-1)!
Sume cu n termeni:suma primelor n numere impare:
De exemplu pentru n=5,sirul primelor 5 numere naturale impare este(1,3,5,7,9),iar numai acestora este S5=1+3+5+7+9.
Observam ca se poae stabili o corespondenta intre rangul unui termen si 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,este0,adica 2*5-1,adica 2*n-1
Pe caz general,sirul primelor n numere naturale impare este (1,3,5,…,2n-1).Notand termenii sirului cu a1,a2,…an,observam ca un termen oarekare ak(de rang k)are valoarea 2*k-1.Vom spune ca sirul de mai sus este definit prin formula termenului general ak=2*k-1.
Suma primelor n numere naturale este Sn=a1+a2+…+an=1+3+5+..+2n-1.
Dca al n-lea termen,cel de rang n,este 2*n-1,atnci al (n-1)-lea termen este 2(n-1)-1,adica 2*n-3.Astfel,Sn=1+3+5+..+(2*n-3)+(2*n-1).Dar 1+3+5+..+(2n-3)reprezinta suma primelor n-1 numere naturale impare notata Sn-1,deci Sn=(2*n-1)+Sn-1.Pentru n=0,avem cazul particular S0=0.Obtinem astfel relatia de recurenta completa:
Sn={0,pt n=0;(2n-1)+Sn-1,pt n>0}
Si aceasta relatie genereaza un algoritm recursiv:pentru a calcula suma Sn,avem nevoie de suma Sn-1.