|

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ă?

  1. 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.
  2. 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

}

  1. 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țieO funcție se apelează pe ea însăși.Două sau mai multe funcții se apelează reciproc.
Exemple comuneFactorial, FibonacciFuncții care validează reguli complexe.
ComplexitateMai simplă de implementat și înțeles.Necesită planificare mai atentă.

4. Exemple practice


Exemplu 1: Determinarea parității unui număr

  1. Problema: Determinați dacă un număr este par sau impar folosind recursivitate indirectă.
  2. 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

  1. Problema: Validarea unui șir care trebuie să alterneze între vocale și consoane.
  2. 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

  1. Problema: Calculați suma numerelor pozitive și negative dintr-un vector, alternând între apeluri.
  2. 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

AvantajeDezavantaje
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

  1. Implementați două funcții recursive indirecte care determină dacă toate cifrele unui număr sunt impare sau pare.
  2. Scrieți un program care folosește recursivitatea indirectă pentru a calcula suma și produsul elementelor unui vector.
  3. Realizați două funcții care validează dacă un șir începe și se termină cu același caracter, alternând apelurile.

7. Scheme logice

  1. Fluxul recursivității indirecte:
    • Start -> Funcția A -> Apelă funcția B -> Apelă funcția A -> Condiție de oprire -> Stop.
  2. 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.

Similar Posts

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *