lectiipenet.ro

Funcții Recursive: “Păpușile Matrioșka” ale Programării

Written by

admin

in

Bun venit la cea mai fascinantă și mai mind-bending lecție din programare! Dacă funcțiile normale sunt ca niște muncitori care-și fac treaba, funcțiile recursive sunt ca păpușile rusești (matrioșka) care se conțin pe ele însele!

1. Ce este Recursivitatea? “Oglinda în Oglindă”

Analogie cu viața reală:
Imaginează-ți că stai între două oglinzi față în față. Ce vezi?

  • O oglindă arată o oglindă care arată o oglindă care arată…
  • Aceasta este recursivitate în natură!

Definiție simplă:

O funcție recursivă este o funcție care se apelează pe ea însăși.

Cum gândește calculatorul:

f(5) = 5 * f(4)
     = 5 * (4 * f(3))
     = 5 * (4 * (3 * f(2)))
     = 5 * (4 * (3 * (2 * f(1))))
     = 5 * (4 * (3 * (2 * 1)))
     = 120

2. Structura unei Funcții Recursive: “Regulile Jocului”

Orice funcție recursivă are DOUĂ părți esențiale:

#include <iostream>
using namespace std;

void functieRecursiva(int n) {
    // 1. CONDIȚIA DE BAZĂ (cazul de oprire)
    // FĂRĂ ASTA - INFINITATE!
    if(n <= 0) {
        return;  // OPREȘTE recursivitatea!
    }

    // 2. APELUL RECURSIV (pasul recursiv)
    // cu un argument MAI MIC
    functieRecursiva(n - 1);
}

int main() {
    functieRecursiva(5);
    return 0;
}

Analogie cu scarile:

void urca_scari(int trepte) {
    if(trepte == 0) {
        cout << "Am ajuns sus!";
        return;
    }

    cout << "Urc o treaptă... " << trepte << " rămase\n";
    urca_scari(trepte - 1);  // Urci și mai apoi urci și mai apoi...
}

3. Primul Exemplu: “Contorul Invers”

#include <iostream>
using namespace std;

// Funcție care numără de la N la 1
void numaraInvers(int n) {
    // CONDIȚIA DE BAZĂ
    if(n <= 0) {
        cout << "GATA!\n";
        return;
    }

    // AFIȘEAZĂ numărul curent
    cout << n << "... ";

    // APELEAZĂ-TE cu numărul MAI MIC
    numaraInvers(n - 1);
}

int main() {
    cout << "=== CONTOR INVERS RECURSIV ===\n\n";

    cout << "Număr de la 5 la 1:\n";
    numaraInvers(5);

    cout << "\nNumăr de la 3 la 1:\n";
    numaraInvers(3);

    return 0;
}

Output:

=== CONTOR INVERS RECURSIV ===

Număr de la 5 la 1:
5... 4... 3... 2... 1... GATA!

Număr de la 3 la 1:
3... 2... 1... GATA!

Cum funcționează în memorie:

numaraInvers(3)
│
├── Afișează: 3...
│   └── numaraInvers(2)
│       │
│       ├── Afișează: 2...
│       │   └── numaraInvers(1)
│       │       │
│       │       ├── Afișează: 1...
│       │       │   └── numaraInvers(0)
│       │       │       │
│       │       │       └── Afișează: GATA!
│       │       └── ← se întoarce
│       └── ← se întoarce
└── ← se întoarce

4. FACTORIAL – Exemplul Clasic

Ce este factorial?

5! = 5 × 4 × 3 × 2 × 1 = 120
4! = 4 × 3 × 2 × 1 = 24
1! = 1
0! = 1  (by definition)

Implementare recursivă:

#include <iostream>
using namespace std;

// Funcție care calculează factorialul
int factorial(int n) {
    // CONDIȚIA DE BAZĂ
    if(n <= 1) {
        return 1;  // 0! = 1 și 1! = 1
    }

    // APEL RECURSIV
    return n * factorial(n - 1);
}

int main() {
    cout << "=== FACTORIAL RECURSIV ===\n\n";

    cout << "Factorialul lui 5:\n";
    cout << "5! = " << factorial(5) << endl;

    cout << "\nCalcul pas cu pas:\n";
    cout << "factorial(5)\n";
    cout << "= 5 * factorial(4)\n";
    cout << "= 5 * (4 * factorial(3))\n";
    cout << "= 5 * (4 * (3 * factorial(2)))\n";
    cout << "= 5 * (4 * (3 * (2 * factorial(1))))\n";
    cout << "= 5 * (4 * (3 * (2 * 1)))\n";
    cout << "= 5 * (4 * (3 * 2))\n";
    cout << "= 5 * (4 * 6)\n";
    cout << "= 5 * 24\n";
    cout << "= 120\n";

    // Teste cu alte numere
    cout << "\nAlte teste:\n";
    cout << "0! = " << factorial(0) << endl;
    cout << "1! = " << factorial(1) << endl;
    cout << "6! = " << factorial(6) << endl;

    return 0;
}

5. FIBONACCI – “Familia de Iepuri”

Șirul lui Fibonacci:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Regula: f(n) = f(n-1) + f(n-2)
#include <iostream>
using namespace std;

int fibonacci(int n) {
    // CONDIȚIILE DE BAZĂ
    if(n == 0) return 0;
    if(n == 1) return 1;

    // APEL RECURSIV DUBLU
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    cout << "=== FIBONACCI RECURSIV ===\n\n";

    cout << "Primii 10 termeni Fibonacci:\n";
    for(int i = 0; i < 10; i++) {
        cout << "f(" << i << ") = " << fibonacci(i) << endl;
    }

    cout << "\nCum se calculează f(4):\n";
    cout << "f(4) = f(3) + f(2)\n";
    cout << "     = (f(2) + f(1)) + (f(1) + f(0))\n";
    cout << "     = ((f(1) + f(0)) + 1) + (1 + 0)\n";
    cout << "     = ((1 + 0) + 1) + 1\n";
    cout << "     = (1 + 1) + 1\n";
    cout << "     = 2 + 1\n";
    cout << "     = 3\n";

    return 0;
}

Problema cu Fibonacci recursiv:

// ATENȚIE! Această implementare este INEFICIENTĂ!
// Calculează aceleași valori de multe ori!

// Pentru n = 5:
// f(5) = f(4) + f(3)
// f(4) = f(3) + f(2)   ← f(3) calculat DIN NOU!
// f(3) = f(2) + f(1)   ← f(2) calculat DIN NOU!
// ... și tot așa...

6. Suma Cifrelor unui Număr

#include <iostream>
using namespace std;

int sumaCifre(int n) {
    // CONDIȚIA DE BAZĂ
    if(n == 0) {
        return 0;
    }

    // APEL RECURSIV
    // Ultima cifră + suma cifrelor rămase
    return (n % 10) + sumaCifre(n / 10);
}

int main() {
    cout << "=== SUMA CIFRELOR RECURSIV ===\n\n";

    int numar = 12345;
    cout << "Suma cifrelor lui " << numar << ":\n";
    cout << sumaCifre(numar) << endl;

    cout << "\nCum funcționează:\n";
    cout << "sumaCifre(12345)\n";
    cout << "= 5 + sumaCifre(1234)\n";
    cout << "= 5 + (4 + sumaCifre(123))\n";
    cout << "= 5 + (4 + (3 + sumaCifre(12)))\n";
    cout << "= 5 + (4 + (3 + (2 + sumaCifre(1))))\n";
    cout << "= 5 + (4 + (3 + (2 + (1 + sumaCifre(0)))))\n";
    cout << "= 5 + (4 + (3 + (2 + (1 + 0))))\n";
    cout << "= 5 + (4 + (3 + (2 + 1)))\n";
    cout << "= 5 + (4 + (3 + 3))\n";
    cout << "= 5 + (4 + 6)\n";
    cout << "= 5 + 10\n";
    cout << "= 15\n";

    return 0;
}

7. CMMDC (Cel Mai Mare Divizor Comun)

Algoritmul lui Euclid:

cmmdc(a, b) = cmmdc(b, a % b)
cmmdc(a, 0) = a
#include <iostream>
using namespace std;

int cmmdc(int a, int b) {
    // CONDIȚIA DE BAZĂ
    if(b == 0) {
        return a;
    }

    // APEL RECURSIV
    return cmmdc(b, a % b);
}

int main() {
    cout << "=== CMMDC RECURSIV (Euclid) ===\n\n";

    cout << "cmmdc(48, 18) = " << cmmdc(48, 18) << endl;
    cout << "cmmdc(56, 98) = " << cmmdc(56, 98) << endl;
    cout << "cmmdc(17, 13) = " << cmmdc(17, 13) << endl;

    cout << "\nExplicație pentru cmmdc(48, 18):\n";
    cout << "cmmdc(48, 18)\n";
    cout << "= cmmdc(18, 48 % 18) = cmmdc(18, 12)\n";
    cout << "= cmmdc(12, 18 % 12) = cmmdc(12, 6)\n";
    cout << "= cmmdc(6, 12 % 6) = cmmdc(6, 0)\n";
    cout << "= 6\n";

    return 0;
}

8. Parcurgerea unui Vector

#include <iostream>
using namespace std;

// Afișează elementele unui vector recursiv
void afiseazaVector(int v[], int n) {
    // CONDIȚIA DE BAZĂ
    if(n == 0) {
        return;
    }

    // Afișează PRIMUL element
    cout << v[0] << " ";

    // Apel recursiv cu RESTUL vectorului
    afiseazaVector(v + 1, n - 1);
}

// Calculează suma elementelor
int sumaVector(int v[], int n) {
    if(n == 0) {
        return 0;
    }

    return v[0] + sumaVector(v + 1, n - 1);
}

// Găsește maximul
int maximVector(int v[], int n) {
    if(n == 1) {
        return v[0];
    }

    int maxRest = maximVector(v + 1, n - 1);

    if(v[0] > maxRest) {
        return v[0];
    } else {
        return maxRest;
    }
}

int main() {
    cout << "=== OPERAȚII CU VECTORI RECURSIV ===\n\n";

    int vector[] = {5, 2, 8, 1, 9, 3};
    int lungime = 6;

    cout << "Vectorul: ";
    afiseazaVector(vector, lungime);
    cout << endl;

    cout << "Suma: " << sumaVector(vector, lungime) << endl;
    cout << "Maxim: " << maximVector(vector, lungime) << endl;

    return 0;
}

9. Turnurile din Hanoi

Problema clasică de recursivitate:

Avem 3 tije: A, B, C
Și n discuri de dimensiuni diferite pe tija A
Reguli:
1. Mută un singur disc odată
2. Nu pune disc mare peste disc mic
3. Mută toate discurile pe tija C
#include <iostream>
using namespace std;

void hanoi(int n, char sursa, char destinatie, char auxiliar) {
    // CONDIȚIA DE BAZĂ
    if(n == 1) {
        cout << "Mută disc 1 de pe " << sursa << " pe " << destinatie << endl;
        return;
    }

    // APELURI RECURSIVE
    // 1. Mută n-1 discuri de pe sursa pe auxiliar
    hanoi(n - 1, sursa, auxiliar, destinatie);

    // 2. Mută discul n de pe sursa pe destinatie
    cout << "Mută disc " << n << " de pe " << sursa << " pe " << destinatie << endl;

    // 3. Mută n-1 discuri de pe auxiliar pe destinatie
    hanoi(n - 1, auxiliar, destinatie, sursa);
}

int main() {
    cout << "=== TURNURILE DIN HANOI ===\n\n";

    cout << "Soluția pentru 3 discuri:\n";
    hanoi(3, 'A', 'C', 'B');

    cout << "\nNumărul minim de mutări pentru n discuri: 2^n - 1\n";
    cout << "3 discuri: 2^3 - 1 = 7 mutări\n";
    cout << "5 discuri: 2^5 - 1 = 31 mutări\n";
    cout << "64 discuri: 2^64 - 1 ≈ 18.4 trilioane mutări!\n";

    return 0;
}

10. Căutarea Binară Recursivă

#include <iostream>
using namespace std;

int cautareBinara(int v[], int stanga, int dreapta, int x) {
    // CONDIȚIA DE BAZĂ
    if(stanga > dreapta) {
        return -1;  // Nu s-a găsit
    }

    // Calculează mijlocul
    int mijloc = stanga + (dreapta - stanga) / 2;

    // Dacă l-am găsit
    if(v[mijloc] == x) {
        return mijloc;
    }

    // Dacă x e mai mic, căutăm în stânga
    if(x < v[mijloc]) {
        return cautareBinara(v, stanga, mijloc - 1, x);
    }

    // Dacă x e mai mare, căutăm în dreapta
    return cautareBinara(v, mijloc + 1, dreapta, x);
}

int main() {
    cout << "=== CĂUTARE BINARĂ RECURSIVĂ ===\n\n";

    int vector[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int lungime = 10;

    int caut = 13;
    int pozitie = cautareBinara(vector, 0, lungime - 1, caut);

    if(pozitie != -1) {
        cout << "Am găsit " << caut << " la poziția " << pozitie << endl;
    } else {
        cout << caut << " nu a fost găsit\n";
    }

    return 0;
}

11. Recursivitate vs Iterativitate

#include <iostream>
using namespace std;

// VERSIUNE RECURSIVĂ
int factorialRecursiv(int n) {
    if(n <= 1) return 1;
    return n * factorialRecursiv(n - 1);
}

// VERSIUNE ITERATIVĂ
int factorialIterativ(int n) {
    int result = 1;
    for(int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

int main() {
    cout << "=== RECURSIV vs ITERATIV ===\n\n";

    cout << "Factorial recursiv vs iterativ:\n";
    cout << "5! recursiv = " << factorialRecursiv(5) << endl;
    cout << "5! iterativ = " << factorialIterativ(5) << endl;

    cout << "\n--- AVANTAJE ---\n";
    cout << "RECURSIVITATE:\n";
    cout << "+ Cod mai elegant și concis\n";
    cout << "+ Natural pentru probleme recursive (arbori, divide-et-impera)\n";
    cout << "+ Mai ușor de înțeles pentru anumite probleme\n\n";

    cout << "ITERATIVITATE:\n";
    cout << "+ Mai rapid (fără overhead de apeluri)\n";
    cout << "+ Folosește mai puțină memorie (fără stack)\n";
    cout << "+ Nu riscă stack overflow\n";

    cout << "\n--- DEZAVANTAJE ---\n";
    cout << "RECURSIVITATE:\n";
    cout << "- Poate cauza stack overflow pentru adâncimi mari\n";
    cout << "- Mai lent din cauza apelurilor de funcții\n";
    cout << "- Consumă mai multă memorie\n\n";

    cout << "ITERATIVITATE:\n";
    cout << "- Cod mai lung și mai complex pentru unele probleme\n";
    cout << "- Mai greu de înțeles pentru algoritmi natural recursivi\n";

    return 0;
}

12. Recursivitate Indirectă: “Dansul Funcțiilor”

#include <iostream>
using namespace std;

// Declarații înainte (forward declarations)
void functieA(int n);
void functieB(int n);

void functieA(int n) {
    if(n <= 0) {
        return;
    }

    cout << "A: " << n << endl;
    functieB(n - 1);
}

void functieB(int n) {
    if(n <= 0) {
        return;
    }

    cout << "B: " << n << endl;
    functieA(n - 1);
}

int main() {
    cout << "=== RECURSIVITATE INDIRECTĂ ===\n\n";

    cout << "A și B se apelează reciproc:\n";
    functieA(5);

    return 0;
}

13. Reguli de Aur pentru Recursivitate

REGULA 1: Mereu ai nevoie de un CAZ DE BAZĂ

// GREȘIT - RECURSIVITATE INFINITĂ!
int factorialGresit(int n) {
    return n * factorialGresit(n - 1);  // NICIODATĂ nu se oprește!
}

// CORECT
int factorialCorect(int n) {
    if(n <= 1) {  // CAZ DE BAZĂ
        return 1;
    }
    return n * factorialCorect(n - 1);
}

REGULA 2: Argumentul trebuie să se apropie de cazul de bază

// GREȘIT
int recursivitateProasta(int n) {
    if(n <= 0) return 0;
    return recursivitateProasta(n);  // La fel ca înainte - INFINIT!
}

// CORECT
int recursivitateBuna(int n) {
    if(n <= 0) return 0;
    return recursivitateBuna(n - 1);  // Se apropie de 0!
}

REGULA 3: Stack Overflow este REAL

int factorialMare(int n) {
    if(n <= 1) return 1;
    return n * factorialMare(n - 1);
}

// factorialMare(10000) va da STACK OVERFLOW!
// Soluție: folosește iterativ pentru numere mari

REGULA 4: Divide et Impera

// Problemele bune pentru recursivitate:
// 1. Se pot împărți în subprobleme mai mici
// 2. Subproblemele sunt similare cu problema inițială
// 3. Există un caz de bază simplu

14. Exerciții Practice

#include <iostream>
using namespace std;

// EXERCIȚIU 1: Inversarea unui șir
void inversareSir(char s[], int start, int end) {
    if(start >= end) {
        return;
    }

    // Schimbă caracterele
    char temp = s[start];
    s[start] = s[end];
    s[end] = temp;

    // Apel recursiv pentru restul
    inversareSir(s, start + 1, end - 1);
}

// EXERCIȚIU 2: Puterea unui număr
int putere(int baza, int exponent) {
    if(exponent == 0) {
        return 1;
    }

    return baza * putere(baza, exponent - 1);
}

// EXERCIȚIU 3: Verifică palindrom
bool estePalindrom(char s[], int start, int end) {
    if(start >= end) {
        return true;
    }

    if(s[start] != s[end]) {
        return false;
    }

    return estePalindrom(s, start + 1, end - 1);
}

int main() {
    cout << "=== EXERCIȚII PRACTICE ===\n\n";

    // Test inversare șir
    char sir[] = "recursivitate";
    cout << "Șir original: " << sir << endl;
    inversareSir(sir, 0, 12);
    cout << "Șir inversat: " << sir << endl;

    // Test putere
    cout << "\n2^5 = " << putere(2, 5) << endl;
    cout << "3^4 = " << putere(3, 4) << endl;

    // Test palindrom
    char palindrom[] = "capac";
    char nonpalindrom[] = "calculator";

    cout << "\nVerificare palindrom:\n";
    cout << "'capac' este palindrom? " 
         << (estePalindrom(palindrom, 0, 4) ? "DA" : "NU") << endl;
    cout << "'calculator' este palindrom? " 
         << (estePalindrom(nonpalindrom, 0, 9) ? "DA" : "NU") << endl;

    return 0;
}

15. Concluzie: Când să Folosești Recursivitatea?

FOLOSEȘTE recursivitate când:

  1. Problema este natural recursivă (arbori, grafuri)
  2. Codul iterativ ar fi foarte complex
  3. Performanța nu este critică
  4. Adâncimea recursivă este mică

EVITĂ recursivitatea când:

  1. Adâncimea poate fi foarte mare (risc stack overflow)
  2. Performanța este critică
  3. Codul iterativ este la fel de simplu

Probleme clasice pentru recursivitate:

✅ Factorial, Fibonacci
✅ Turnurile din Hanoi
✅ Parcurgerea arborilor
✅ Divide et impera (QuickSort, MergeSort)
✅ Backtracking

// Ultimul sfat:
// Recursivitatea este ca un superputere.
// Folosește-o cu înțelepciune!

// Când e bine folosită, creează cod elegant și puternic.
// Când e prost folosită, creează probleme grave.

// Exersază, înțelege, și folosește cu discernământ!
// Happy recursive coding! 🔄🎯

Remember: Recursivitatea nu este doar o tehnică de programare – este un mod de gândire! Învață să vezi problemele ca fiind compuse din versiuni mai mici ale lor însele, și vei deveni un programator mult mai bun!

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

More posts