|

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?

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

  1. Definiție:
    • O funcție este direct recursivă dacă se apelează pe ea însăși în interiorul definiției sale.
  2. Exemplu simplu:

void functieRecursiva() {

    cout << „Aceasta este o functie recursiva directa.” << endl;

    functieRecursiva(); // Apel direct recursiv

}

  1. Utilizare:
    • Calcularea factorialului.
    • Seria Fibonacci.
    • Parcurgerea structurilor de date, cum ar fi arborii.

4. Avantajele și dezavantajele recursivității

AvantajeDezavantaje
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

  1. Definiție matematică:
    n!=n⋅(n−1)!n! = n \cdot (n – 1)!n!=n⋅(n−1)!, cu 0!=10! = 10!=1.
  2. 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

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

  1. Problema: Calculați suma elementelor unui vector folosind recursivitatea.
  2. 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)

  1. Problema: Parcurgeți un arbore binar folosind recursivitatea.
  2. 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

  1. Calcularea puterii unui număr: xn=x⋅xn−1x^n = x \cdot x^{n-1}xn=x⋅xn−1.
  2. Determinarea cifrei maxime dintr-un număr.
  3. Inversarea unui șir de caractere.

7. Activități practice pentru elevi

  1. Scrieți o funcție recursivă care calculează suma cifrelor unui număr.
  2. Implementați o funcție recursivă care verifică dacă un șir este palindrom.
  3. Scrieți o funcție recursivă care calculează valoarea maximă dintr-un vector.

8. Scheme logice

  1. Funcție recursivă:
    • Start -> Verificare caz de bază -> Apel funcție pe subproblemă -> Combinare rezultat -> Stop.
  2. 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.

Similar Posts

Lasă un răspuns

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