Caz de bază — unde se oprește recursivitatea

De ce contează?

Imaginează-ți că cobori o scară pe întuneric, treaptă cu treaptă. La un moment dat piciorul tău atinge podeaua — știi că ai ajuns jos și te oprești. Aceea e ultima treaptă. Dacă scara n-ar avea capăt, ai coborî la nesfârșit. La recursivitate, „ultima treaptă” se numește caz de bază: locul unde te oprești din coborât.

Ce este cazul de bază și de ce e obligatoriu

Știi deja că o funcție recursivă se apelează pe ea însăși cu o problemă mai mică. Dar dacă tot reduci problema, unde te oprești? Răspunsul: la cazul de bază — problema atât de mică încât îi cunoști răspunsul direct, fără niciun alt apel.

Orice recursivitate corectă are două părți care lucrează împreună:

cazul de bază — condiția de oprire; aici returnezi un răspuns fix;
pasul recursiv — aici reduci problema și te apelezi din nou.

Cazul de bază nu e un detaliu opțional. El e frâna. Pasul recursiv coboară mereu spre probleme mai mici; cazul de bază e singurul care spune „gata, stop”. Fără el, apelurile coboară la infinit: fiecare apel începe altul, care începe altul, și așa mai departe — programul nu se mai termină niciodată singur.

Exemplu pas cu pas

Factorial — un singur caz de bază

Reamintește-ți definiția: n! = n × (n-1)!, iar 0! = 1. Acel 0! = 1 este cazul de bază. Hai să urmărim factorial(3):

factorial(3) → are nevoie de factorial(2)
factorial(2) → are nevoie de factorial(1)
factorial(1) → are nevoie de factorial(0)
factorial(0) → caz de bază, răspund direct 1, mă opresc

Abia când am atins cazul de bază, lanțul se întoarce și calculează: 1 → 1 → 2 → 6. Fără linia 0! = 1, ultimul apel ar fi cerut factorial(-1), apoi factorial(-2), la nesfârșit.

Fibonacci — DOUĂ cazuri de bază

La Fibonacci, fiecare termen e suma celor doi dinainte: fib(n) = fib(n-1) + fib(n-2). Pasul recursiv coboară cu doi pași deodată, deci o singură treaptă de oprire nu ajunge. Ai nevoie de două: fib(0) = 0 și fib(1) = 1.

De ce două? Dacă te-ai opri doar la fib(0), ramura care cere fib(2-1) = fib(1) ar continua spre fib(1-2) = fib(-1) și ai pierde controlul. Cu ambele cazuri de bază, fiecare ramură se închide la timp:

fib(2) = fib(1) + fib(0) = 1 + 0 = 1 (ambele opriri atinse direct)
fib(3) = fib(2) + fib(1) = 1 + 1 = 2

Implementare C++

#include <iostream>
using namespace std;

long long factorial(int n) {
    if (n == 0) return 1;          // caz de baza: 0! = 1
    return n * factorial(n - 1);   // pas recursiv
}

long long fibonacci(int n) {
    if (n == 0) return 0;          // primul caz de baza
    if (n == 1) return 1;          // al doilea caz de baza
    return fibonacci(n - 1) + fibonacci(n - 2);  // pas recursiv
}

int main() {
    cout << factorial(3) << "\n";   // 6
    cout << factorial(5) << "\n";   // 120
    cout << fibonacci(0) << "\n";   // 0
    cout << fibonacci(1) << "\n";   // 1
    cout << fibonacci(7) << "\n";   // 13
    return 0;
}

Observă structura: la fiecare funcție, verificarea cazului de bază vine prima, înaintea apelului recursiv. Așa garantezi că oprirea e testată la fiecare apel.

Ce se întâmplă fără caz de bază

Hai să stricăm intenționat funcția factorial, scoțând oprirea:

long long factorialGresit(int n) {
    return n * factorialGresit(n - 1);  // GRESIT: nu se opreste niciodata
}

Apelul factorialGresit(3) cere factorialGresit(2), care cere factorialGresit(1), apoi factorialGresit(0), factorialGresit(-1), factorialGresit(-2)... Nimic nu spune vreodată „stop”. Fiecare apel deschis ocupă puțină memorie pe stiva de apeluri, iar memoria e limitată. Când se umple, programul se prăbușește cu stack overflow — eroarea clasică a recursivității fără caz de bază (sau cu unul pe care nu îl atinge niciodată).

Observația-cheie

Numărul cazurilor de bază depinde de câți pași coboară pasul recursiv. Factorialul coboară cu un pas (n-1) și are nevoie de un caz de bază. Fibonacci coboară cu doi pași (n-1 și n-2) și are nevoie de două. Regula practică: trebuie să oprești TOATE ramurile înainte ca ele să treacă pe sub valoarea cea mai mică validă.

Greșeli frecvente

Lipsește complet cazul de bază: funcția se apelează la infinit → stack overflow. Scrie oprirea ÎNAINTE de pasul recursiv, la fiecare funcție recursivă.
Condiție de oprire care nu se atinge niciodată: dacă testezi n == 0 dar cobori cu n - 2 plecând de la un număr impar, sari peste 0 și ajungi la valori negative. Verifică n <= 0, nu doar n == 0, când nu ești sigur că nimerești fix.
Un singur caz de bază la Fibonacci: cu doar fib(0) = 0, ramura spre fib(1) scapă spre fib(-1). Ai nevoie de DOUĂ opriri, fib(0) și fib(1).
Recursie pe valori negative neoprită: dacă cineva apelează factorial(-3), testul n == 0 nu se atinge. Protejează intrarea sau folosește n <= 0.

Diagrama de mai jos arată unde se află cazurile de bază față de pasul recursiv, pentru Fibonacci. Primele două celule sunt opriri directe; restul se calculează:

fib	0	1	1	2	3	5	8
	0	1	2	3	4	5	6
	baza	baza					recursiv

fib(0) și fib(1) sunt cazuri de bază (răspuns direct). Restul rezultă din pasul recursiv.

Recapitulare

Cazul de bază e problema atât de mică încât răspunzi direct, fără alt apel — el oprește coborârea recursivă.
Fără caz de bază (sau cu unul greșit, care nu se atinge), apelurile merg la infinit și programul se prăbușește cu stack overflow.
Numărul cazurilor de bază depinde de pasul recursiv: factorialul are nevoie de unul (0! = 1), Fibonacci de două (fib(0) = 0, fib(1) = 1).