Subprograme Recursive – Funcții Direct Recursive în C++ 14
1. Obiectivele lecției:
- Să înțeleagă conceptul de funcții recursive.
- Să înțeleagă ce sunt funcțiile direct recursive.
- Să implementeze exemple practice care folosesc recursivitatea directă pentru a rezolva probleme.
2. Ce este recursivitatea?
- Definiție:
- Recursivitatea este o tehnică de programare în care o funcție se apelează pe ea însăși pentru a rezolva o problemă prin divizarea acesteia în subprobleme mai simple.
- Condiții necesare pentru o funcție recursivă:
- Cazul de bază: O condiție care oprește recursivitatea.
- Cazul recursiv: Funcția se apelează pe ea însăși cu o versiune mai simplă a problemei.
3. Ce sunt funcțiile direct recursive?
- Definiție:
- O funcție este direct recursivă dacă se apelează pe ea însăși în interiorul definiției sale.
- Exemplu simplu:
void functieRecursiva() {
cout << „Aceasta este o functie recursiva directa.” << endl;
functieRecursiva(); // Apel direct recursiv
}
- Utilizare:
- Calcularea factorialului.
- Seria Fibonacci.
- Parcurgerea structurilor de date, cum ar fi arborii.
4. Avantajele și dezavantajele recursivității
Avantaje | Dezavantaje |
Simplifică soluția pentru probleme complexe. | Poate duce la depășirea stivei de apeluri (stack overflow). |
Cod mai concis și mai lizibil pentru probleme recursive. | Consumă mai multă memorie din cauza apelurilor recursive. |
Ușor de aplicat pentru probleme de tip divide-and-conquer. | Performanță mai slabă decât soluțiile iterative în anumite cazuri. |
5. Exemple practice
Exemplu 1: Calcularea Factorialului
- Definiție matematică:
n!=n⋅(n−1)!n! = n \cdot (n – 1)!n!=n⋅(n−1)!, cu 0!=10! = 10!=1. - Implementare:
#include <iostream>
using namespace std;
int factorial(int n) {
if (n == 0) {
return 1; // Cazul de bază
}
return n * factorial(n – 1); // Apel recursiv
}
int main() {
int numar = 5;
cout << „Factorial de ” << numar << ” este: ” << factorial(numar) << endl;
return 0;
}
Exemplu 2: Seria Fibonacci
- Definiție matematică:
F(n)=F(n−1)+F(n−2)F(n) = F(n – 1) + F(n – 2)F(n)=F(n−1)+F(n−2), cu F(0)=0F(0) = 0F(0)=0 și F(1)=1F(1) = 1F(1)=1. - Implementare:
#include <iostream>
using namespace std;
int fibonacci(int n) {
if (n == 0) {
return 0; // Cazul de bază
}
if (n == 1) {
return 1; // Cazul de bază
}
return fibonacci(n – 1) + fibonacci(n – 2); // Apel recursiv
}
int main() {
int numar = 6;
cout << „Al ” << numar << „-lea număr din seria Fibonacci este: ” << fibonacci(numar) << endl;
return 0;
}
Exemplu 3: Suma elementelor unui vector
- Problema: Calculați suma elementelor unui vector folosind recursivitatea.
- Implementare:
#include <iostream>
using namespace std;
int sumaVector(int vec[], int dim) {
if (dim == 0) {
return 0; // Cazul de bază
}
return vec[dim – 1] + sumaVector(vec, dim – 1); // Apel recursiv
}
int main() {
int vector[] = {1, 2, 3, 4, 5};
int dim = 5;
cout << „Suma elementelor este: ” << sumaVector(vector, dim) << endl;
return 0;
}
Exemplu 4: Parcurgerea unui arbore binar (preordine)
- Problema: Parcurgeți un arbore binar folosind recursivitatea.
- Implementare:
#include <iostream>
using namespace std;
struct Nod {
int valoare;
Nod* stanga;
Nod* dreapta;
};
void parcurgePreordine(Nod* radacina) {
if (radacina == NULL) {
return; // Cazul de bază
}
cout << radacina->valoare << ” „;
parcurgePreordine(radacina->stanga); // Apel recursiv
parcurgePreordine(radacina->dreapta); // Apel recursiv
}
int main() {
Nod* radacina = new Nod{1, new Nod{2, NULL, NULL}, new Nod{3, NULL, NULL}};
cout << „Parcurgerea preordine: „;
parcurgePreordine(radacina);
return 0;
}
6. Probleme tipice rezolvate cu recursivitate
- Calcularea puterii unui număr: xn=x⋅xn−1x^n = x \cdot x^{n-1}xn=x⋅xn−1.
- Determinarea cifrei maxime dintr-un număr.
- Inversarea unui șir de caractere.
7. Activități practice pentru elevi
- Scrieți o funcție recursivă care calculează suma cifrelor unui număr.
- Implementați o funcție recursivă care verifică dacă un șir este palindrom.
- Scrieți o funcție recursivă care calculează valoarea maximă dintr-un vector.
8. Scheme logice
- Funcție recursivă:
- Start -> Verificare caz de bază -> Apel funcție pe subproblemă -> Combinare rezultat -> Stop.
- Funcție direct recursivă pentru factorial:
- Start -> Dacă n==0n == 0n==0, returnează 1 -> Apel recursiv n∗factorial(n−1)n * factorial(n – 1)n∗factorial(n−1) -> Stop.
9. Concluzie
- Funcțiile directe recursive sunt o soluție elegantă pentru probleme de tip divide-and-conquer.
- Este important să definim corect cazul de bază pentru a evita buclele infinite.
- Practica ajută la înțelegerea recursivității și la utilizarea acesteia în mod eficient.