Programare Competitivă

Recursivitate pe vectori

Vectorii sunt structuri ideale pentru recursivitate: fiecare operație poate fi gândită ca “rezolvă pentru primul element + rezolvă recursiv pentru restul vectorului”.

Idee generală

Pentru un vector v[1..n] (indexat de la 1), putem:

  • Împărți în “primul element” + “restul vectorului” (v[2..n])
  • Împărți în “ultimul element” + “restul vectorului” (v[1..n-1])
  • Împărți în “prima jumătate” + “a doua jumătate”

De obicei, folosim un parametru i (indicele curent) pentru a parcurge vectorul.

1. Suma elementelor

Definiție recursivă

suma(v, i, n) = suma(v, i+1, n) + v[i], pentru i <= n
suma(v, n+1, n) = 0  (am depasit ultimul element)

Cod

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

int v[1001];
int n;

int suma(int i) {
    if (i > n) return 0;     // am depasit ultimul element
    return v[i] + suma(i + 1);
}

int main() {
    fin >> n;
    for (int i = 1; i <= n; i++) fin >> v[i];
    fout << suma(1);
    return 0;
}

date.in:

5
10 20 30 40 50

date.out:

150

Pas cu pas

suma(1) = v[1] + suma(2) = 10 + 140 = 150
suma(2) = v[2] + suma(3) = 20 + 120 = 140
suma(3) = v[3] + suma(4) = 30 + 90  = 120
suma(4) = v[4] + suma(5) = 40 + 50  = 90
suma(5) = v[5] + suma(6) = 50 + 0   = 50
suma(6) = 0

2. Maximul dintr-un vector

Definiție recursivă

max(v, i) = maximul dintre v[i] și maximul vectorului v[i+1..n].

Cod

int maxim(int i) {
    if (i == n) return v[i];          // ultim element - el insusi e maxim
    int m = maxim(i + 1);
    return v[i] > m ? v[i] : m;
}

// Apel initial: maxim(1)

Pas cu pas pentru v = [3, 7, 2, 8, 1] (indici 1..5)

maxim(1): v[1]=3 vs max(v[2..5]) = 3 vs 8 → 8
maxim(2): v[2]=7 vs max(v[3..5]) = 7 vs 8 → 8
maxim(3): v[3]=2 vs max(v[4..5]) = 2 vs 8 → 8
maxim(4): v[4]=8 vs max(v[5..5]) = 8 vs 1 → 8
maxim(5): v[5]=1 → 1

3. Căutare liniară

Verificăm dacă x se află în vector.

Cod

bool cautare(int i, int x) {
    if (i > n) return false;          // vector epuizat
    if (v[i] == x) return true;       // gasit!
    return cautare(i + 1, x);
}

// Apel initial: cautare(1, x)

Complexitate: O(n) timp, O(n) spațiu stivă.

4. Căutare binară recursivă

Vectorul trebuie sortat. La fiecare pas, eliminăm jumătate.

Definiție recursivă

caut_bin(v, x, st, dr):
  - dacă st > dr: x nu există
  - mij = (st + dr) / 2
  - dacă v[mij] == x: gata
  - dacă v[mij] > x: caut in stanga
  - dacă v[mij] < x: caut in dreapta

Cod

int cautBin(int x, int st, int dr) {
    if (st > dr) return -1;
    int mij = (st + dr) / 2;
    if (v[mij] == x) return mij;
    if (v[mij] > x) return cautBin(x, st, mij - 1);
    return cautBin(x, mij + 1, dr);
}

// Apel initial: cautBin(x, 1, n)

Complexitate: O(log n) - eliminăm jumătate la fiecare pas.

Pas cu pas pentru v = [1, 3, 5, 7, 9, 11, 13] (indici 1..7), căutăm 7

cautBin(7, 1, 7): mij=4, v[4]=7 → gasit la indice 4!

Pentru căutăm 4:

cautBin(4, 1, 7): mij=4, v[4]=7 > 4 → cautBin(4, 1, 3)
cautBin(4, 1, 3): mij=2, v[2]=3 < 4 → cautBin(4, 3, 3)
cautBin(4, 3, 3): mij=3, v[3]=5 > 4 → cautBin(4, 3, 2)
cautBin(4, 3, 2): st > dr → -1 (nu exista)

5. Numărul de apariții ale unei valori

Cod

int nrAparitii(int i, int x) {
    if (i > n) return 0;
    int rest = nrAparitii(i + 1, x);
    if (v[i] == x) return rest + 1;
    return rest;
}

// Apel initial: nrAparitii(1, x)

Varianta alternativă (mai compactă)

int nrAparitii(int i, int x) {
    if (i > n) return 0;
    return (v[i] == x ? 1 : 0) + nrAparitii(i + 1, x);
}

6. Verificare palindrom (vector)

Un vector e palindrom dacă e identic cu el însuși citit de la dreapta la stânga.

Definiție recursivă

  • Dacă există cel mult 1 element între capete: palindrom
  • Dacă v[st] != v[dr]: nu e palindrom
  • Altfel: verifică v[st+1..dr-1]

Cod

bool palindrom(int st, int dr) {
    if (st >= dr) return true;
    if (v[st] != v[dr]) return false;
    return palindrom(st + 1, dr - 1);
}

// Apel initial: palindrom(1, n)

Pas cu pas pentru v = [1, 2, 3, 2, 1] (indici 1..5)

palindrom(1, 5): v[1]=1 == v[5]=1 → palindrom(2, 4)
palindrom(2, 4): v[2]=2 == v[4]=2 → palindrom(3, 3)
palindrom(3, 3): st == dr → true

Pentru v = [1, 2, 3, 4] (indici 1..4):

palindrom(1, 4): v[1]=1 != v[4]=4 → false

7. Inversare vector

Inversăm “pe loc” vectorul.

Cod

void inverseaza(int st, int dr) {
    if (st >= dr) return;
    int tmp = v[st]; v[st] = v[dr]; v[dr] = tmp;
    inverseaza(st + 1, dr - 1);
}

// Apel initial: inverseaza(1, n)

Pentru v = [1, 2, 3, 4, 5] (indici 1..5):

Start: [1, 2, 3, 4, 5]
inverseaza(1, 5): swap v[1], v[5] → [5, 2, 3, 4, 1]
inverseaza(2, 4): swap v[2], v[4] → [5, 4, 3, 2, 1]
inverseaza(3, 3): st == dr, return

8. Cel mai mare divizor comun al vectorului

gcd pentru un vector = gcd-ul reducerii pas cu pas.

Cod

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

int gcdVector(int i) {
    if (i == n) return v[i];
    return gcd(v[i], gcdVector(i + 1));
}

// Apel initial: gcdVector(1)

Pentru v = [12, 18, 24] (indici 1..3):

gcdVector(1) = gcd(12, gcdVector(2)) = gcd(12, 6) = 6
gcdVector(2) = gcd(18, gcdVector(3)) = gcd(18, 24) = 6
gcdVector(3) = v[3] = 24

9. Verificare vector sortat

Cod

bool esteSortat(int i) {
    if (i == n) return true;            // ultimul - nimic de verificat
    if (v[i] > v[i + 1]) return false;
    return esteSortat(i + 1);
}

// Apel initial: esteSortat(1)

Cod complet

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

int v[1001];
int n;

int suma(int i) { return i > n ? 0 : v[i] + suma(i + 1); }

int maxim(int i) {
    if (i == n) return v[i];
    int m = maxim(i + 1);
    return v[i] > m ? v[i] : m;
}

bool palindrom(int st, int dr) {
    if (st >= dr) return true;
    if (v[st] != v[dr]) return false;
    return palindrom(st + 1, dr - 1);
}

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

    fout << "Suma: " << suma(1) << "\n";
    fout << "Maxim: " << maxim(1) << "\n";
    fout << "Palindrom: " << (palindrom(1, n) ? "DA" : "NU") << "\n";

    return 0;
}

date.in:

5
1 2 3 2 1

date.out:

Suma: 9
Maxim: 3
Palindrom: DA

Iterativ vs recursiv pe vectori

Pentru majoritatea operațiilor liniare pe vectori (sumă, max, căutare), iterativul e mai bun:

  • Nu consumă stiva
  • Overhead mai mic

Recursivitatea e valoroasă când:

  • Algoritmul e natural divide-et-impera (merge sort, quick sort, căutare binară)
  • Procesezi arbori sau grafuri (DFS)
  • Învăți să gândești recursiv

Greșeli frecvente

1. Indicele depășește vectorul

int maxim(int i) {
    if (i > n) return v[i]; // v[n+1] nu exista!
    ...
}

Caz de bază corect: if (i == n) return v[i] sau if (i > n) return INT_MIN.

2. Uitarea parametrului de indice

int suma() {
    if (???) ...
    return v[???] + suma();
}

Fără parametru, recursivitatea nu poate “înainta”. Mereu un parametru de indice (sau start/end pentru intervale).

3. Stack overflow pentru n mare

Pentru n = 100,000 și recursivitate liniară, stiva se umple. Folosește iterativ sau recursivitate cu adâncime logaritmică (tip divide et impera).

4. Palindrom greșit

bool palindrom(int st, int dr) {
    if (st == dr) return true; // doar pentru n impar!
    ...
}

Trebuie st >= dr (acoperă și st > dr când capetele se “intersectează” la vectori pari).

5. Apel initial cu indice greșit

// Vectori indexati de la 1:
suma(0);  // GRESIT - v[0] nu exista
suma(1);  // CORECT

Atenție: citirea și apelul inițial trebuie să folosească același sistem de indexare (1-based).

Ce să reții

  • Vectorii se prestează natural la recursivitate prin parametrul indice.
  • În acest manual folosim indexare de la 1 - citim v[1..n], apelăm cu i = 1, condiția de bază e i > n (sau i == n pentru ultimul).
  • Operații tipice: suma, maxim, căutare, palindrom, inversare, verificare sortare.
  • Căutarea binară recursivă e O(log n), cea liniară e O(n).
  • Pentru n mic, recursivitatea e clară. Pentru n mare, preferă iterativ (risc de stack overflow).
  • Pattern-ul general: parametru indice + caz de bază la capăt + reducere cu 1 la fiecare apel.
Cuprins Inapoi Inainte