Subprograme Recursive – Funcții Indirect Recursive în C++ 15
1. Obiectivele lecției:
- Să înțeleagă conceptul de funcții indirect recursive.
- Să învețe diferențele dintre recursivitatea directă și cea indirectă.
- Să implementeze exemple practice de funcții indirect recursive.
2. Ce este recursivitatea indirectă?
- Definiție:
- Recursivitatea indirectă apare atunci când o funcție A apelează o funcție B, iar funcția B apelează din nou funcția A. Astfel, funcțiile implicate se apelează reciproc pentru a rezolva problema.
- Structura generală:
void A() {
// Operații
B(); // Funcția A apelează funcția B
}
void B() {
// Operații
A(); // Funcția B apelează funcția A
}
- Cerințe pentru recursivitatea indirectă:
- Definirea unui caz de bază pentru a opri apelurile recursive.
- Asigurarea unei secvențe finite de apeluri între funcții.
3. Diferența dintre recursivitatea directă și indirectă
Caracteristică | Recursivitate directă | Recursivitate indirectă |
Definiție | O funcție se apelează pe ea însăși. | Două sau mai multe funcții se apelează reciproc. |
Exemple comune | Factorial, Fibonacci | Funcții care validează reguli complexe. |
Complexitate | Mai simplă de implementat și înțeles. | Necesită planificare mai atentă. |
4. Exemple practice
Exemplu 1: Determinarea parității unui număr
- Problema: Determinați dacă un număr este par sau impar folosind recursivitate indirectă.
- Implementare:
#include <iostream>
using namespace std;
void esteImpar(int n);
void estePar(int n) {
if (n == 0) {
cout << „Numărul este par.” << endl;
return; // Caz de bază
}
esteImpar(n – 1); // Apel recursiv indirect
}
void esteImpar(int n) {
if (n == 0) {
cout << „Numărul este impar.” << endl;
return; // Caz de bază
}
estePar(n – 1); // Apel recursiv indirect
}
int main() {
int numar = 5;
estePar(numar); // Pornește determinarea
return 0;
}
Exemplu 2: Validarea unei secvențe de reguli
- Problema: Validarea unui șir care trebuie să alterneze între vocale și consoane.
- Implementare:
#include <iostream>
#include <cstring>
using namespace std;
void verificaConsoana(const char* sir, int index);
void verificaVocala(const char* sir, int index) {
if (sir[index] == ‘\0’) {
cout << „Șirul este valid.” << endl;
return; // Caz de bază
}
if (strchr(„aeiouAEIOU”, sir[index])) {
verificaConsoana(sir, index + 1); // Apel recursiv indirect
} else {
cout << „Șir invalid: așteptam o vocală la poziția ” << index << endl;
}
}
void verificaConsoana(const char* sir, int index) {
if (sir[index] == ‘\0’) {
cout << „Șirul este valid.” << endl;
return; // Caz de bază
}
if (!strchr(„aeiouAEIOU”, sir[index])) {
verificaVocala(sir, index + 1); // Apel recursiv indirect
} else {
cout << „Șir invalid: așteptam o consoană la poziția ” << index << endl;
}
}
int main() {
const char* sir = „aBcDeF”;
verificaVocala(sir, 0); // Pornește validarea
return 0;
}
Exemplu 3: Calculul sumelor alternative
- Problema: Calculați suma numerelor pozitive și negative dintr-un vector, alternând între apeluri.
- Implementare:
#include <iostream>
using namespace std;
int sumaNegative(const int vec[], int dim, int index);
int sumaPozitive(const int vec[], int dim, int index) {
if (index == dim) {
return 0; // Caz de bază
}
if (vec[index] > 0) {
return vec[index] + sumaNegative(vec, dim, index + 1); // Apel recursiv indirect
}
return sumaNegative(vec, dim, index + 1);
}
int sumaNegative(const int vec[], int dim, int index) {
if (index == dim) {
return 0; // Caz de bază
}
if (vec[index] < 0) {
return vec[index] + sumaPozitive(vec, dim, index + 1); // Apel recursiv indirect
}
return sumaPozitive(vec, dim, index + 1);
}
int main() {
int vector[] = {1, -2, 3, -4, 5};
int dim = 5;
int suma = sumaPozitive(vector, dim, 0);
cout << „Suma totală este: ” << suma << endl;
return 0;
}
5. Avantaje și dezavantaje ale recursivității indirecte
Avantaje | Dezavantaje |
Permite modelarea unor probleme complexe în mod elegant. | Poate fi dificil de urmărit fluxul de apeluri. |
Poate simplifica implementarea unor reguli interdependente. | Performanță mai scăzută decât soluțiile iterative. |
Ajută la separarea logicii în funcții mai mici și clare. | Crește riscul de depășire a stivei de apeluri. |
6. Activități practice pentru elevi
- Implementați două funcții recursive indirecte care determină dacă toate cifrele unui număr sunt impare sau pare.
- Scrieți un program care folosește recursivitatea indirectă pentru a calcula suma și produsul elementelor unui vector.
- Realizați două funcții care validează dacă un șir începe și se termină cu același caracter, alternând apelurile.
7. Scheme logice
- Fluxul recursivității indirecte:
- Start -> Funcția A -> Apelă funcția B -> Apelă funcția A -> Condiție de oprire -> Stop.
- Diagrama de apeluri:
A -> B -> A -> … -> Stop
8. Concluzie
- Recursivitatea indirectă este o tehnică utilă pentru probleme complexe care implică relații între mai multe funcții.
- Este important să definim clar cazul de bază pentru a preveni buclele infinite.
- Separarea logicii între funcții ajută la claritatea și modularitatea codului.