Rezolvarea subproblemelor — recursie până la bază

De ce contează?

Ești șeful unei echipe mari și ai de numărat sacii dintr-un depozit imens. Nu îi numeri tu pe toți. Împarți depozitul în două și dai fiecare jumătate câte unui adjunct: „numără-ți partea ta și spune-mi totalul”. Adjunctul face exact la fel — își împarte zona și deleagă mai departe. Lanțul coboară până când cineva primește un singur raft cu un singur sac: pe acela îl numără singur, pe loc. Apoi răspunsurile urcă înapoi și se adună. Tu ai încredere că fiecare adjunct îți dă un total corect — nu te duci să verifici. Asta e rezolvarea recursivă a subproblemelor.

Pasul de rezolvare: apel recursiv pe fiecare jumătate

Presupunem că împărțirea s-a făcut deja (e subiectul altei lecții): intervalul [st, dr] se taie la mijloc în două jumătăți, [st, mid] și [mid + 1, dr]. Pasul de rezolvare — partea de conquer — înseamnă un singur lucru: chemi aceeași funcție pe fiecare jumătate.

rezolva(st, mid) se ocupă de stânga, rezolva(mid + 1, dr) se ocupă de dreapta. Fiecare apel primește un interval strict mai mic decât cel curent, deci ne apropiem de ceva minuscul.

Coborârea nu poate continua la nesfârșit. Există o subproblemă atât de mică încât nu mai are sens să o tai: un singur element, adică st == dr. Acela este cazul de bază — îl rezolvi direct, fără niciun alt apel. Pentru o sumă, suma unui singur element este chiar acel element.

„Saltul de credință”

Aici e partea care derutează la început. Când scrii apelul rezolva(st, mid), ai impulsul să verifici în minte cum anume va calcula el răspunsul. Nu face asta.

Presupui pur și simplu că apelul recursiv întoarce deja rezultatul corect pentru jumătatea lui. Te porți cu el ca și cum ar fi o funcție gata făcută, scrisă de altcineva, în care ai deplină încredere. Acesta este saltul de credință al recursivității.

De ce ai voie? Pentru că ai garantat două lucruri: cazul de bază e corect (cea mai mică problemă e rezolvată direct), iar fiecare apel coboară spre el (intervalul se micșorează mereu). Dacă baza e corectă și pașii se apropie de bază, atunci, prin inducție, toate apelurile sunt corecte — inclusiv cele de jos pe care te bazezi.

Efectul practic: scapi de povara de a urmări tot lanțul în cap. Tot ce-ți rămâne de gândit este: „am rezultatul stâng și rezultatul drept, ce fac cu ele?”. (Acel „ce fac cu ele” este combinarea — subiectul altei lecții.)

Exemplu pas cu pas: suma unui vector prin D&I

Vrem suma elementelor v = [4, 2, 7, 1], pe indicii 0..3. Relația recursivă este:

suma(st, dr) = suma(st, mid) + suma(mid + 1, dr)

cu mid = st + (dr - st) / 2. Cazul de bază: suma(st, st) = v[st].

Coborârea (împărțim mereu până la un element):

suma(0, 3) cere suma(0, 1) și suma(2, 3)
suma(0, 1) cere suma(0, 0) și suma(1, 1)
suma(2, 3) cere suma(2, 2) și suma(3, 3)

Cazurile de bază (le rezolvi direct, fără alt apel):

suma(0, 0) = 4, suma(1, 1) = 2, suma(2, 2) = 7, suma(3, 3) = 1

Acum urcăm — și aici aplici saltul de credință: ai încredere în valorile de jos și doar le aduni:

suma(0, 1) = 4 + 2 = 6
suma(2, 3) = 7 + 1 = 8
suma(0, 3) = 6 + 8 = 14

Rezultat: 14. Observă că nu ai numărat niciodată mai mult de un element „cu mâna ta”: tot restul s-a făcut din încrederea în apeluri.

Implementare C++

#include <iostream>
using namespace std;

// suma elementelor din v[st..dr] prin divide et impera
int suma(int v[], int st, int dr) {
    if (st == dr) return v[st];          // caz de baza: un singur element
    int mid = st + (dr - st) / 2;        // mijloc, fara risc de overflow
    int sumaStanga = suma(v, st, mid);   // increderea: returneaza corect
    int sumaDreapta = suma(v, mid + 1, dr);
    return sumaStanga + sumaDreapta;     // combinarea (alta lectie)
}

int main() {
    int v[] = {4, 2, 7, 1};
    int n = 4;
    cout << suma(v, 0, n - 1) << "\n";   // 14
    return 0;
}

Toată coborârea și urcarea sunt ascunse în cele două apeluri recursive. Tu scrii doar trei lucruri: cazul de bază, cele două apeluri și combinarea lor.

Observația-cheie

Cazul de bază este subproblema indivizibilă — atât de mică încât nu mai are sens să o împarți. La un vector, acela este un singur element (st == dr). El este și sursa tuturor rezultatelor corecte: din el pornește încrederea care urcă, nivel cu nivel, până la răspunsul final.

Greșeli frecvente

Lipsește cazul de bază: scrii direct cele două apeluri fără if (st == dr). Intervalul nu se mai oprește din micșorat, apelurile se acumulează pe stivă la nesfârșit și obții stack overflow.
Nu te încrezi în recursie și complici: încerci să desfaci în minte fiecare apel, adaugi bucle suplimentare sau variabile globale „ca să fii sigur”. Saltul de credință există tocmai ca să nu faci asta — apelul recursiv întoarce deja corect.
Caz de bază greșit (st > dr): folosești intervalul gol drept prag în loc de st == dr. Pentru un singur element ai accesa apoi un interval invalid, iar logica „un element = v[st]” dispare; rezultatul devine greșit sau ai acces în afara vectorului.
Apel recursiv pe același interval: scrii din greșeală suma(v, st, dr) în loc de jumătăți, sau uiți mid + 1 și apelezi suma(v, mid, dr). Subproblema nu se micșorează, deci nu atingi niciodată cazul de bază — iar recursie infinită.

v	4	2	7	1
	0	1	2	3
	st			dr

suma(0, 3) se taie în [0,1] și [2,3], apoi fiecare în câte un element (cazul de bază). La urcare: 6 + 8 = 14.

Recapitulare

Pasul de rezolvare (conquer) înseamnă un apel recursiv pe fiecare subproblemă; coborârea se oprește la cazul de bază, subproblema indivizibilă (un element).
Saltul de credință: presupui că apelurile recursive întorc deja rezultatul corect, fiindcă baza e corectă și fiecare pas se apropie de ea.
Astfel îți rămâne de gândit doar ce faci cu cele două rezultate (combinarea) — subiectul lecției următoare.