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
Top Related