RECURSIVITATE (functii recursive)

Prof. Jiduc Gabriel

RECURSIVITATE

• Functia recursiva este o functie care se autoapeleaza (in corpul ei de instructiuni exista o apelare a functiei)

• Ex: int funct_rec (int n)

{

………

a=a+funct_rec(n-1);

………

}

RECURSIVITATE

• O functie recursiva este utilizata:

– Pentru calculul unei expresii matematice recursive

Ex: sirul lui Fibonacci:

– Cand este creat algoritmul de rezolvare al unei probleme pentru un anumit nivel si acesta poate fi generalizat pentru orice nivel

Ex: cautarea binara (intr-un sir ordonat)

RECURSIVITATE

• O functie recursiva trebuie sa contina in corpul ei o conditie care sa opreasca autoapelarea (altfel se intra intr-o bucla infinita)

• In general aceasta conditie se introduce la inceputul corpului functiei cu ajutorul unei structuri de decizie if

• Observatie: in general un algoritm recursiv poate fi transformat intr-un algoritm iterativ cu ajutorul unei structuri repetitive

RECURSIVITATE • Exemplu: calculul factorialului unui nunar intreg • int factorial (int k) { if k==1 return 1; else return k*factorial(k-1); } void main() { int n; cin>>n; cout<<factorial(n); }

RECURSIVITATE

• Schema de lucru:

– Memoria de lucru a calculatorului:

• Memoria statica: pentru variabilele globale, ale functiei principale (main)

• Memoria stiva: pentru variabilele functiilor programului, apelate de functia principala

• Memoria dinamica: pentru variabilele alocate dinamic (in timpul rularii programului)

Memoria statica

Memoria stiva (STACK)

Memoria dinamica (HEAP)

RECURSIVITATE • Schema de lucru:

– Mecanismului folosirii stivei in cazul problemei factorialului numarului n (presupunem n=4)

– Observatie:

• dupa returnarea rezultatului unei apelari recursive zona din stiva a acelei apelari se elimina

• Ex: dupa P5 in memoria stiva numai exista zona corespunzatoare lui factorial(1), dar exista zonele corespunzatoare factorial(2), factorial(3) si factorial(4)

n=4 factorial(4) afiseaza 24

main()

4=1? NU 4*factorial

(3) return 4*6

factorial(4)

3=1? NU 3*factorial

(2) return 3*2

2=1? NU 2*factorial

(1) return 2*1

1=1? DA return 1

factorial(3) factorial(2) factorial(1)

P1 P2 P3 P4

P5 P6 P7 P8