Algoritmi recursivi

Recursivitatea a apărut din necesităţi practice, cum ar fi transcrierea directă a formulelor matematice recursive. Un exemplu de formulă matematică recursivă este următoarea:

(n+1)! = (n+1) · n!, pentru n≥0

0! = 1 (prin convenţie)

Valorile unei funcţii recursive se calculează din aproape în aproape, pe baza valorilor cunoscute ale funcţiei pentru anumite argumente iniţiale. Pentru a calcula noile valori ale funcţiei recursive, trebuie memorate valorile deja calculate care sunt strict necesare. Acest fapt face ca implementarea în program a calculului unor funcţii recursive să necesite un volum mare de memorie.

Exemplu de funcţie recursivă: funcţia n! pe care o notăm cu factorial, factorial:NN si care se defineşte recursiv astfel

factorial(n) =

Pentru a calcula factorial(4):

factorial(4)  4 · factorial(3) 4 · 3 · factorial(2) 4 · 3 · 2 · factorial(1) 4 · 3 · 2 · 1 · factorial(0) 4 · 3 · 2 · 1 · 1 = 4!

Exemplu:

Enunţul problemei: Să se descrie un algoritm pentru determinarea sumei factorialelor până la nN* dat, folosind o funcţie recursivă pentru calculul factorialului.

Rezolvare: Problema se reduce la calcul unei sume: S =  .

 

Descrierea algoritmului în pseudocod:

functie factorial(n)

daca n=0 sau n=1 atunci

returneaza 1

altfel

returneaza n·factorial(n-1)

sfarsit

 

citeşte n

S ¬ 0

pentru i = 1,n,1  repeta

  S ¬ S + factorial(i)

scrie S

 

Descrierea algoritmului în C++:

#include <iostream.h>

int n,i;

float S;

float factorial(int n)

{

if (n==0) return 1;

//else

return n*factorial(n-1);

}

void main() {

cout<<endl<<“Dati valoarea lui n (n>=1): “;

cin>>n; //* presupunem ca n>=1

for (i=1;i<=n;i++) S += factorial(i);

cout<<“Suma factorialelor pana la “<<n<<“: “<<S;

}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s