Ce este recursivitatea?

Recursivitatea e o tehnică în care o funcție se apelează pe sine, cu date mai mici, pentru a rezolva o problemă mai complexă.

Idea de bază: “pentru a rezolva problema mare, rezolvă o versiune mai mică și folosește rezultatul ei”.

Analogie: păpușile matrioșka

Imaginează-ți o păpușă matrioșka. Ca să găsești cea mai mică păpușă:

1. Deschide păpușa cea mare.
2. Dacă înăuntru e o altă păpușă, repetă procesul cu ea (ca și cum ar fi altă păpușă mare).
3. Dacă nu mai e nimic înăuntru, ai găsit cea mai mică - oprește-te.

Asta e recursivitate. Ai o operație (deschiderea unei păpuși) și o condiție de oprire (nu mai e nimic înăuntru).

Structura unei funcții recursive

Orice funcție recursivă are două părți:

1. Cazul de bază (condiția de oprire) - situația simplă, rezolvată direct, fără apel recursiv.
2. Cazul recursiv - problema se reduce la o variantă mai mică, iar funcția se apelează pe sine.

tip functie(parametri) {
    if (caz_de_baza) {
        // Rezolva direct, fara apel recursiv
        return raspuns_simplu;
    }
    // Apel recursiv cu date "mai mici"
    return ... functie(date_mai_mici) ...;
}

Exemplul 1: suma de la 1 la n

Vrem să calculăm S(n) = 1 + 2 + 3 + ... + n.

Definiția recursivă

S(n) = S(n-1) + n, pentru n >= 1
S(0) = 0

Suma de la 1 la n e suma de la 1 la n-1 plus n. Iar suma de la 1 la 0 e 0 (cazul de bază).

Cod

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int suma(int n) {
    if (n == 0) return 0;        // caz de baza
    return suma(n - 1) + n;      // caz recursiv
}

int main() {
    int n;
    fin >> n;
    fout << suma(n);
    return 0;
}

date.in:

5

date.out:

15

Cum se execută suma(5)?

suma(5) = suma(4) + 5
suma(4) = suma(3) + 4
suma(3) = suma(2) + 3
suma(2) = suma(1) + 2
suma(1) = suma(0) + 1
suma(0) = 0           ← caz de baza
suma(1) = 0 + 1 = 1
suma(2) = 1 + 2 = 3
suma(3) = 3 + 3 = 6
suma(4) = 6 + 4 = 10
suma(5) = 10 + 5 = 15

Apelurile se fac “în adâncime” până la cazul de bază, apoi rezultatele se “întorc” unul câte unul.

Exemplul 2: factorial

n! = 1 * 2 * 3 * ... * n. Definiție recursivă:

n! = n * (n-1)!, pentru n >= 1
0! = 1

Cod

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

Pentru factorial(4):

4! = 4 * 3! = 4 * 6 = 24
3! = 3 * 2! = 3 * 2 = 6
2! = 2 * 1! = 2 * 1 = 2
1! = 1 * 0! = 1 * 1 = 1
0! = 1

De ce e utilă recursivitatea?

1. Exprimă natural problemele definite recursiv

Multe probleme matematice (factorial, Fibonacci, CMMDC) sunt definite recursiv. Codul seamănă perfect cu definiția.

2. Împarte problema în subprobleme

Problema mare se reduce la una mai mică până devine trivială. Paradigma “divide et impera” se bazează pe asta.

3. Cod mai scurt și mai clar

Unele probleme (traversare de arbori, backtracking, DFS în graf) sunt mult mai ușor de scris recursiv decât iterativ.

Ce NU e recursivitate

Atenție: o funcție care se apelează pe sine fără condiție de oprire intră în buclă infinită - asta nu e recursivitate corectă.

int gresit(int n) {
    return gresit(n - 1) + 1; // NICI O CONDITIE DE OPRIRE!
}

Programul va crăpa cu stack overflow - epuizează memoria stivei.

Recursivitatea vs Iterativ

Pentru suma 1..n putem scrie și iterativ:

int suma(int n) {
    int s = 0;
    for (int i = 1; i <= n; i++) s += i;
    return s;
}

Pentru probleme simple, iterativul e mai bun. Pentru arbori, backtracking, DFS - recursivul e natural.

Greșeli frecvente

1. Lipsa cazului de bază

int f(int n) {
    return f(n - 1) + 1; // bucla infinita
}

Mereu scrie primul cazul de bază, apoi cazul recursiv.

2. Cazul de bază nu e atins

int f(int n) {
    if (n == 0) return 0;
    return f(n - 2) + 1; // pentru n impar, nu ajunge la 0!
}

Pentru n = 5: f(3) → f(1) → f(-1) → f(-3) → ... - stack overflow.

Testează: pentru orice intrare validă, apelurile ajung la cazul de bază?

3. Apel recursiv cu date mai mari (sau egale)

int f(int n) {
    if (n == 0) return 0;
    return f(n + 1); // bucla infinita!
}

Apelul recursiv trebuie să micșoreze problema.

4. Stack overflow pentru n mare

Recursivitatea simplă are limită la ~10^4-105 apeluri (limita stivei sistemului). Pentru valori mai mari, folosește iterativ sau coadă/stivă explicită.

Ce să reții

• Recursivitatea = o funcție se apelează pe sine cu date mai mici.
• Structură: caz de bază (oprire) + caz recursiv (apel pe sine).
• Fiecare apel recursiv trebuie să se apropie de cazul de bază.
• Exemple clasice: suma 1..n, factorial, CMMDC, Fibonacci.
• Codul recursiv e des mai apropiat de definiția matematică.
• Atenție la lipsa cazului de bază și la apelurile care nu se micșorează.
• Recursivitatea folosește memorie O(adâncime) din stiva de apeluri.