Reducerea schemelor de recurenta

Burtea Bogdan-FlorianGr. 405

Definitie

Recurenta in informatica este o metoda a carei solutii depinde de solutia altor probleme mai mici ale aceleasi probleme. Aceasta abordare poate fi aplicata mai multor tipuri de probleme. Recurenta este una dintre ideile principale ale informaticii.

• O recurenta contine un set de valori initiale• x0 = b0 x1 = b1 … xk = bk

• si o formula recursive• xk = a(xn-1, xn-2, … , x0) pentru n>k

• de la care putem calcula valoarea lui xn, pentru orice n>k, de la valoarile intiale

Functii recursive si algoritmi

O tactica obisnuita folosita este pentru a imparti o problema in probleme mai mici la fel cu cea originala. Rezolvand aceste probleme mai mici si combinand rezultatele, vom gasi un raspuns la problema mare.

Definita unei functii recursive contine una sau mai multe valori initiale pentru care functia returneaza un rezultat fara a folosi recurenta si unul sau mai multe cazuri pentru care programul foloseste recurenta. Un exemplu este functia factorial pentru care 0!=1 si pentru orice n>0, n!=n(n-1)!.

Un subprogram recursiv trebuie sa respecte urmatoarele reguli:• subprogramul trebuie sa poata fi executat,

celputin intr-o situatie, fara a se autoapela;• subprogramul recursiv se va autoapela intr-un

mod in care se tinde spre ajungerea in situatia de executie fara autoapel.

Tipuri de recurenta

Recurenta simpla si recurenta multipla

Recurenta ce contine o singura apelare a propriei functii este cunoscuta ca recurenta simpla, pe cand recurenta ce contine mai multe apelari a propriei functii este cunoscuta ca recurenta multipla. Exemple standard ale recurentei simple ar fi cautarea lineara sau functia factorial, pe cand un exemplu standard al recurentei multiple ar fi sirulul lui Fibonacci.

Recurenta indirecta

Exemplele de baza ale recurentei folosesc recurenta directa, unde o functie se apeleaza singura. Recurenta indirecta apare atunci cand o functie este apelata nu de ea, ci de o alta functie.

Programe recursive

Factorial

Formula:

Cod:Fact=1;For(i=1;i<=n;i++){Fact=fact*i;} Cod recursiv:Int fact(int n){if n=0 return 1;else return n*fact(n-1);}

Sirul lui Fibonacci

Formula:

Valori initiale:

Cod recursiv:int fib(int x) { if (x == 0) return 0; if (x == 1) return 1; return fib(x-1)+fib(x-2);}

O reducere a acestei scheme de recurenta ar fi aceasta formula: