Recursivitate multiplă și Fill recursiv (DFS)

Până acum, funcțiile noastre recursive făceau un singur apel pe sine. Dar multe probleme au nevoie de mai multe apeluri - asta se numește recursivitate multiplă.

Un caz important e Fill recursiv / DFS - parcurgerea unui “spațiu” (matrice, graf, arbore) prin apeluri pe direcții diferite.

1. Recursivitate multiplă: Fibonacci

Fibonacci e cel mai simplu exemplu de recursivitate multiplă:

F(n) = F(n-1) + F(n-2)

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

Fiecare apel face două apeluri recursive. Numărul total de apeluri crește exponențial.

Arborele de apeluri pentru `fib(4)`

              fib(4)
             /      \
         fib(3)    fib(2)
         /    \     /   \
      fib(2) fib(1) fib(1) fib(0)
      /   \
   fib(1) fib(0)

fib(4) → 9 apeluri
fib(30) → ~2.7 milioane apeluri
fib(40) → ~331 milioane apeluri

De aceea Fibonacci naiv e lent - aceleași valori se calculează de multe ori.

Memoizarea - cum salvăm Fibonacci

Memoizarea e tehnica prin care salvăm rezultatele calculate într-o zonă de memorie (vector, map) și le refolosim când avem nevoie de aceeași valoare.

Ideea

La Fibonacci naiv, fib(3) e calculat de 2 ori, fib(2) de 3 ori, fib(1) de 5 ori, etc. - tot la nesfârșit.

Soluția: prima dată când calculăm fib(k), salvăm rezultatul într-un vector memo[k]. A doua oară când avem nevoie de fib(k), citim direct din memo[k] - O(1), nu recalculăm.

Cod

long long memo[101];
bool calculat[101]; // sau inițializezi memo cu -1

long long fib(int n) {
    if (n <= 1) return n;
    if (calculat[n]) return memo[n];  // deja calculat - returnam
    calculat[n] = true;
    return memo[n] = fib(n - 1) + fib(n - 2);
}

Sau mai compact, folosim -1 ca marcaj pentru “necalculat”:

long long memo[101];  // initializat cu -1

long long fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

// In main:
for (int i = 0; i <= 100; i++) memo[i] = -1;

Cum transformă memoizarea complexitatea?

Fără memoizare

Arborele de apeluri pentru fib(5):

                fib(5)
               /      \
           fib(4)    fib(3)
          /    \     /    \
       fib(3) fib(2) fib(2) fib(1)
       /   \    /  \
    fib(2) fib(1) ... ...

Fiecare nod al arborelui = un apel. Pentru fib(n), numărul total de noduri e ~2^n → O(2^n).

Cu memoizare

              fib(5)
             /      \
         fib(4)    fib(3) ← deja în memo, O(1)
         /    \
      fib(3)  fib(2) ← deja în memo
      /   \
   fib(2) fib(1) ← deja în memo
   /   \
fib(1) fib(0)

Fiecare valoare fib(k) e calculată o singură dată - apoi e citită direct. Total:

n + 1 calcule reale (fib(0), fib(1), …, fib(n))
O(n) apeluri totale

Complexitate: O(n) timp, O(n) memorie.

Comparație

n	Fibonacci naiv	Cu memoizare
10	~177 apeluri	~10 calcule
30	~2.7 milioane	~30 calcule
40	~330 milioane	~40 calcule
50	~40 miliarde (imposibil)	~50 calcule

Memoizarea transformă algoritm exponențial în liniar. Un pas esențial spre programare dinamică.

Cod complet: Fibonacci cu memoizare

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

const int NMAX = 101;
long long memo[NMAX];

long long fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

int main() {
    int n;
    fin >> n;

    for (int i = 0; i < NMAX; i++) memo[i] = -1;

    fout << fib(n);
    return 0;
}

date.in:

date.out:

12586269025

Calculat instant, comparativ cu fibonacci naiv care ar lua ore întregi pentru n = 50.

Memoizarea vs programare dinamică (DP)

Memoizarea e DP de sus în jos (top-down) - pornești cu problema mare, cobori recursiv, salvezi pe drum. E “lazy” - calculezi doar ce ai nevoie.

DP-ul clasic iterativ (tabulare) e de jos în sus (bottom-up) - pornești cu cazurile mici, urci tabelul. E “eager” - calculezi tot.

Ambele dau aceeași complexitate O(n), dar memoizarea e mai intuitivă pentru cei care gândesc recursiv.

2. Drumuri într-o matrice

Problema

O grilă n × m indexată de la 1. Pornești din colțul (1, 1) și vrei să ajungi în (n, m). Poți merge doar jos sau dreapta. Câte drumuri distincte sunt?

Definiție recursivă

drumuri(i, j) = drumuri(i-1, j) + drumuri(i, j-1)
Caz de baza:
  - drumuri(1, 1) = 1
  - drumuri(i, j) = 0 daca i < 1 sau j < 1

Cod

int drumuri(int i, int j) {
    if (i < 1 || j < 1) return 0;
    if (i == 1 && j == 1) return 1;
    return drumuri(i - 1, j) + drumuri(i, j - 1);
}

// Apel initial: drumuri(n, m)

Complexitate: O(2^(n+m)) naiv. Pentru grile mari, folosim memoization (DP).

3. Puteri cu recursivitate multiplă

Ridicare la putere rapidă folosește două apeluri pe cazul par? Nu, doar unul:

long long putere(long long a, int n) {
    if (n == 0) return 1;
    long long jum = putere(a, n / 2);
    if (n % 2 == 0) return jum * jum;
    return a * jum * jum;
}

Observație: calculăm putere(a, n/2) o singură dată și îl folosim de două ori. Asta o face O(log n), nu O(n).

Fill recursiv (DFS) pe matrice

Fill recursiv e tehnica de a “umple” o regiune dintr-o matrice pornind de la o celulă și extinzându-te în toate direcțiile valide. E fundamental pentru:

Algoritmul “flood fill” (paint bucket din Paint)
Detectarea componentelor conexe
Algoritmul lui Lee (drum cel mai scurt)

Problema: numărăm componentele conexe

Enunț

O matrice n × m cu valori 0 și 1, indexată de la 1. Două celule cu 1 sunt conexe dacă sunt vecine (sus, jos, stânga, dreapta). Câte componente conexe sunt?

Matrice:
1 1 0 0 1
1 0 0 1 1
0 0 1 0 0
0 1 1 0 1

Componente: 4

Strategia: DFS de la fiecare celulă nevizitată

Parcurgem matricea.
Când găsim un 1 nevizitat, incrementăm contorul și pornim DFS de la el.
DFS marchează toate celulele din aceeași componentă ca vizitate.

Cod: fill recursiv pe matrice

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

int a[102][102];
bool viz[102][102];
int n, m;

// Cele 4 directii: sus, jos, stanga, dreapta
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

void fill(int x, int y) {
    // Verificari de validitate (matrice indexata de la 1 la n, respectiv 1 la m)
    if (x < 1 || x > n || y < 1 || y > m) return;
    if (viz[x][y] || a[x][y] == 0) return;

    viz[x][y] = true;

    // Apelam recursiv in toate 4 directiile
    for (int d = 0; d < 4; d++)
        fill(x + dx[d], y + dy[d]);
}

int main() {
    fin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            fin >> a[i][j];

    int componente = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (a[i][j] == 1 && !viz[i][j]) {
                componente++;
                fill(i, j);
            }

    fout << componente;
    return 0;
}

date.in:

date.out:

Cum funcționează fill?

Pornind din (1, 1) pe matricea:

DFS merge:

(1,1) viz, apeleaza (sus: afara), (jos: 2,1), (stanga: afara), (dreapta: 1,2)
  (2,1) viz, apeleaza (1,1 vizitat), (3,1 e 0), (afara), (2,2 e 0)
  (1,2) viz, apeleaza (afara), (2,2 e 0), (1,1 vizitat), (1,3 e 0)

Componenta 1 terminată: {(1,1), (2,1), (1,2)}.

Apoi continuăm parcurgerea matricei până găsim alt 1 nevizitat, etc.

Varianta compactă (fără dx/dy)

void fill(int x, int y) {
    if (x < 1 || x > n || y < 1 || y > m) return;
    if (viz[x][y] || a[x][y] == 0) return;
    viz[x][y] = true;
    fill(x - 1, y);
    fill(x + 1, y);
    fill(x, y - 1);
    fill(x, y + 1);
}

Mai explicit, dar mai repetitiv. Varianta cu dx/dy scalează mai ușor (8 direcții, diagonal etc.).

Aplicații clasice ale fill-ului

1. Insule pe o hartă

Matrice cu 1 = uscat, 0 = apă. Câte insule (componente) sunt? → fill recursiv.

2. Flood fill (umplere cu culoare)

Ca bucket tool din Paint: pornești dintr-o celulă și schimbi culoarea pentru toată zona conexă.

void flood(int x, int y, int culoareVeche, int culoareNoua) {
    if (x < 1 || x > n || y < 1 || y > m) return;
    if (a[x][y] != culoareVeche) return;
    a[x][y] = culoareNoua;
    flood(x + 1, y, culoareVeche, culoareNoua);
    flood(x - 1, y, culoareVeche, culoareNoua);
    flood(x, y + 1, culoareVeche, culoareNoua);
    flood(x, y - 1, culoareVeche, culoareNoua);
}

3. Detectarea ariei maxime

Pentru fiecare componentă, calculăm câte celule are. Întoarcem maximul:

int aria;

void fill(int x, int y) {
    if (x < 1 || x > n || y < 1 || y > m) return;
    if (viz[x][y] || a[x][y] == 0) return;
    viz[x][y] = true;
    aria++;
    fill(x + 1, y);
    fill(x - 1, y);
    fill(x, y + 1);
    fill(x, y - 1);
}

// In main:
int ariaMax = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        if (a[i][j] == 1 && !viz[i][j]) {
            aria = 0;
            fill(i, j);
            if (aria > ariaMax) ariaMax = aria;
        }

DFS pe graf

Pentru un graf reprezentat cu liste de adiacență (noduri indexate de la 1):

vector<int> adj[100001];
bool viz[100001];

void dfs(int nod) {
    viz[nod] = true;
    for (int vecin : adj[nod])
        if (!viz[vecin])
            dfs(vecin);
}

Aceeași idee ca fill-ul pe matrice, dar vecinii sunt definiți explicit prin liste.

Aplicație: numărăm componentele conexe într-un graf

int componente = 0;
for (int i = 1; i <= n; i++)
    if (!viz[i]) {
        componente++;
        dfs(i);
    }

Diferența recursivitate multiplă vs liniară

	Liniară	Multiplă
Apeluri/nivel	1	2 sau mai multe
Arborele apelurilor	lanț	arbore
Complexitate	O(n) tipic	O(2^n) tipic fără memoizare
Exemple	suma, factorial	Fibonacci, drumuri, DFS

Recursivitatea multiplă crește exponențial fără optimizări. Dar pentru DFS (fiecare celulă/nod vizitat o dată), rămâne eficient.

Pas cu pas: DFS pe o matrice mică

Matrice 3 × 3 (indici 1..3):

1 0 1
0 1 1
1 1 0

DFS pornind din (1, 1):

fill(1,1): viz[1][1]=true
  fill(0,1): iesi (x invalid)
  fill(2,1):  a[2][1]=0 → iesi
  fill(1,0): iesi
  fill(1,2):  a[1][2]=0 → iesi
Componenta 1: {(1,1)}

Continuăm parcurgerea. Găsim (1,3):

fill(1,3): viz=true
  fill(0,3): iesi
  fill(2,3): a=1, viz=true
    fill(1,3): vizitat
    fill(3,3): a=0 → iesi
    fill(2,2): a=1, viz=true
      fill(1,2): a=0 → iesi
      fill(3,2): a=1, viz=true
        fill(2,2): vizitat
        fill(4,2): iesi
        fill(3,1): a=1, viz=true
          fill(2,1): a=0 → iesi
          fill(4,1): iesi
          fill(3,0): iesi
          fill(3,2): vizitat
        fill(3,3): a=0 → iesi
      fill(2,1): a=0 → iesi
      fill(2,3): vizitat
    fill(2,1): a=0 → iesi
    fill(2,4): iesi
  fill(1,2): a=0 → iesi
  fill(1,4): iesi
Componenta 2: {(1,3), (2,2), (2,3), (3,1), (3,2)}

Total: 2 componente.

Greșeli frecvente

1. Uitarea marcării `viz`

void fill(int x, int y) {
    // viz[x][y] = true; // UITAT!
    fill(x + 1, y);
    ...
}

Fără marcaj, DFS intră în buclă infinită (sau stack overflow).

2. Verificarea limitelor la final

void fill(int x, int y) {
    viz[x][y] = true;
    // ...
    if (x < 1 || x > n) return; // PREA TÂRZIU
}

Pune verificarea limitelor la început, înainte să accesezi a[x][y] sau viz[x][y].

3. Accesare out-of-bounds

if (a[x][y] == 1 && x >= 1 && ...) // x < 1 deja a crasat!

Ordinea corectă: verifică limitele înainte de accesare.

4. Matricea prea mare → stack overflow

Pentru o matrice 10000 × 10000, fill recursiv poate epuiza stiva. Alternative:

BFS iterativ cu coadă explicită (algoritmul lui Lee)
Mărește stiva sistemului (compilator-specific)

5. Vecinii greșiți

Pentru 4 direcții:

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

Pentru 8 direcții (inclusiv diagonale):

int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

Atenție ce direcții permite problema!

6. Limitele pentru indexare de la 1

if (x < 0 || x >= n) return;  // GRESIT pentru indexare de la 1
if (x < 1 || x > n) return;   // CORECT pentru indexare de la 1

Dacă citești cu for (int i = 1; i <= n; i++), verifică limitele cu < 1 și > n.

Ce să reții

Recursivitate multiplă = o funcție face mai multe apeluri pe sine (Fibonacci, DFS, drumuri).
Fără optimizări, poate fi exponențială (Fibonacci: O(2^n)).
Fill recursiv / DFS parcurge o matrice sau graf în adâncime.
În acest manual folosim indexare de la 1 pentru matrici: a[1..n][1..m], condițiile de limită devin x < 1 || x > n.
Aplicații: componente conexe, flood fill, arii, algoritmul lui Lee.
Pattern: verifică limitele → verifică condiția → marchează vizitat → apelează în toate direcțiile.
Pentru grafuri mari, folosește BFS iterativ (evită stack overflow).
DFS pe matrice 4 direcții (sus, jos, stânga, dreapta) sau 8 direcții (și diagonale).