Lectie 7.1.1 Algoritmi recursivi in C++: 5 exemple explicate

Introducere

In acest articol, vom explora conceptul de algoritmi recursivi in limbajul de programare C++. Vom analiza cinci exemple practice pentru a intelege cum functioneaza acesti algoritmi si cum pot fi utilizati pentru rezolvarea problemelor complexe.

1. Calcularea factorialului unui numar

Unul dintre cele mai simple exemple de algoritmi recursivi este calcularea factorialului unui numar. Factorialul unui numar n se calculeaza prin inmultirea tuturor numerelor de la 1 la n.

#include <iostream>
using namespace std;

int factorial(int n) {
    if (n == 0) {
        return 1;
    }
    else {
        return n * factorial(n - 1);
    }
}

int main() {
    int numar;
    cout <> numar;
    cout << "Factorialul numarului " << numar << " este: " << factorial(numar) << endl;
    return 0;
}

2. Calcularea numarului Fibonacci

Numarul Fibonacci este o secventa de numere in care fiecare numar este suma celor doua numere anterioare. Un algoritm recursiv poate fi utilizat pentru a calcula numarul Fibonacci al unui anumit index.

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

int main() {
    int index;
    cout <> index;
    cout << "Numarul Fibonacci al indexului " << index << " este: " << fibonacci(index) << endl;
    return 0;
}

3. Verificarea palindromului

Un palindrom este un cuvant sau o propozitie care poate fi citit in ambele directii. Un algoritm recursiv poate fi utilizat pentru a verifica daca un cuvant este palindrom.

#include <iostream>
#include <string>
using namespace std;

bool palindrom(string cuvant, int stanga, int dreapta) {
    if (stanga >= dreapta) {
        return true;
    }
    if (cuvant[stanga] != cuvant[dreapta]) {
        return false;
    }
    return palindrom(cuvant, stanga + 1, dreapta - 1);
}

int main() {
    string cuvant;
    cout <> cuvant;
    if (palindrom(cuvant, 0, cuvant.length() - 1)) {
        cout << "Cuvantul " << cuvant << " este palindrom." << endl;
    }
    else {
        cout << "Cuvantul " << cuvant << " nu este palindrom." << endl;
    }
    return 0;
}

4. Afisarea numerelor de la 1 la n

Un alt exemplu de algoritm recursiv este afisarea numerelor de la 1 la n. Acest algoritm foloseste o functie recursiva pentru a afisa numerele in ordine crescatoare.

#include <iostream>
using namespace std;

void afisareNumere(int n) {
    if (n > 0) {
        afisareNumere(n - 1);
        cout << n << " ";
    }
}

int main() {
    int numar;
    cout <> numar;
    cout << "Numerele de la 1 la " << numar << " sunt: ";
    afisareNumere(numar);
    cout << endl;
    return 0;
}

5. Calcularea sumei elementelor unui vector

Un algoritm recursiv poate fi utilizat pentru a calcula suma elementelor unui vector. Acesta se bazeaza pe ideea de a aduna elementul curent cu suma elementelor ramase.

#include <iostream>
using namespace std;

int sumaVector(int vector[], int n) {
    if (n <= 0) {
        return 0;
    }
    else {
        return vector[n - 1] + sumaVector(vector, n - 1);
    }
}

int main() {
    int n;
    cout <> n;
    int vector[n];
    cout << "Introduceti elementele vectorului: ";
    for (int i = 0; i > vector[i];
    }
    cout << "Suma elementelor vectorului este: " << sumaVector(vector, n) << endl;
    return 0;
}

Concluzie

Algoritmii recursivi sunt o metoda puternica de rezolvare a problemelor complexe. Ei permit rezolvarea problemelor prin divizarea lor in subprobleme mai mici si rezolvarea acestora recursiv. Cu toate acestea, trebuie utilizati cu atentie pentru a evita situatiile de recursie infinita si pentru a asigura eficienta algoritmului.

In acest articol, am explorat cinci exemple de algoritmi recursivi in limbajul de programare C++. Aceste exemple acopera diferite probleme si demonstreaza puterea si versatilitatea algoritmilor recursivi.

Sper ca acest articol v-a fost util si v-a ajutat sa intelegi mai bine conceptul de algoritmi recursivi in C++. Daca aveti intrebari sau nelamuriri, va rog sa le mentionati in comentarii.