Recursivitate pe tablouri

Aceleași parcurgeri, scrise recursiv: cum alegi parametrul care se micșorează și cum returnezi un rezultat construit din bucăți.

Parametrul care se micșorează

La numere, cazul mai mic apărea de la sine: n / 10, n - 1. La vectori alegi tu ce se micșorează, de obicei indicele curent.

Ai două variante, amândouă corecte:

De la stânga la dreapta, cu indice care crește spre n:

int suma(int v[], int i, int n) {
    if (i > n) return 0;
    return v[i] + suma(v, i + 1, n);
}
// apel: suma(v, 1, n)

De la dreapta la stânga, cu un singur indice care scade:

int suma(int v[], int n) {
    if (n == 0) return 0;
    return v[n] + suma(v, n - 1);
}
// apel: suma(v, n)

A doua are un parametru mai puțin și un caz de bază mai simplu. Când enunțul nu impune antetul, alege-o pe aceasta.

Aceleași probleme, scrise recursiv

Maximul

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

Cazul de bază este n == 1, nu n == 0, pentru că un vector gol nu are maxim. Dacă enunțul permite n = 0, tratezi cazul separat, în afara funcției.

Observă că maxim(v, n-1) se apelează o singură dată și rezultatul se păstrează în m. Dacă l-ai apela de două ori (o dată în comparație și o dată în return), ai dubla munca la fiecare nivel și timpul ar crește exploziv. E aceeași greșeală ca la Fibonacci naiv.

Numărarea

int catePare(int v[], int n) {
    if (n == 0) return 0;
    int rest = catePare(v, n - 1);
    if (v[n] % 2 == 0) return rest + 1;
    return rest;
}

Căutarea

bool exista(int v[], int n, int x) {
    if (n == 0) return false;
    if (v[n] == x) return true;
    return exista(v, n - 1, x);
}

Apar iar cele două cazuri de bază, unul de eșec și unul de succes. Testul de succes se face înaintea apelului, deci căutarea se oprește imediat ce a găsit valoarea.

Afișarea în ambele ordini

Vectorul se poate afișa invers fără să-l răstorni:

void afiseaza(int v[], int n) {
    if (n == 0) return;
    cout << v[n] << " ";
    afiseaza(v, n - 1);
}

Dacă muți cout după apel, se afișează în ordinea normală:

void afiseaza(int v[], int n) {
    if (n == 0) return;
    afiseaza(v, n - 1);
    cout << v[n] << " ";
}

E exact diferența „înainte sau după apel" din lecția precedentă, aplicată pe vector. Scrie-le pe amândouă o dată pe hârtie, ca să ți se fixeze.

Verificarea de palindrom

Aici se micșorează ambele capete deodată:

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

Cazul de bază st >= dr acoperă ambele situații de oprire: vector de lungime pară (capetele se încrucișează) și de lungime impară (se întâlnesc la mijloc).

Căutarea binară recursivă

Căutarea binară are o definiție recursivă naturală, pentru că problema se reduce la o jumătate din vector:

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

Față de varianta cu while, aceasta se citește aproape ca definiția în cuvinte. Aici recursivitatea chiar te ajută.

Cum alegi antetul

Când scrii singur un subprogram recursiv pe vector, întreabă-te:

Ce se micșorează? De obicei n sau un indice.
Când se oprește? Vector gol (n == 0), un singur element (n == 1) sau indici încrucișați.
Ce returnează cazul de bază? Elementul neutru: 0 pentru sumă, 1 pentru produs, true pentru „toate au proprietatea", false pentru „există unul".

Cea mai frecventă greșeală aici e un element neutru greșit. Pentru „toate elementele sunt pare", vectorul gol trebuie să răspundă true, nu false.

De reținut

Micșorează n și lucrează cu v[n]. Ai un parametru în loc de doi.
Apelează recursiv o singură dată și păstrează rezultatul într-o variabilă.
Lucrul înainte de apel dă o ordine, după apel dă ordinea inversă.
Pentru capete care se apropie, cazul de bază este st >= dr.
Cazul de bază returnează elementul neutru al operației.