Modul 10 — Recursivitate · Clasa a X-a Fable

Cele două reguli de aur

Orice funcție recursivă corectă are exact aceste două ingrediente — dacă lipsește unul, programul moare.

① Cazul de bază

Situația atât de simplă încât răspunsul se dă DIRECT, fără alt apel. Păpușa plină din mijloc. fact(1) = 1. Fără el, apelurile nu se opresc niciodată.

② Cazul general → progres

Reduce problema la una STRICT MAI MICĂ: fact(n) = n · fact(n−1). Fiecare apel trebuie să se APROPIE de cazul de bază — altfel, tot infinit.

Legătura cu clasa a IX-a: știi deja să definești subprograme (funcții C++ și def în Python). Singura noutate: în corpul funcției apare… chiar funcția. Mecanismul de apel e identic — doar că se stivuiește.

Stiva de apeluri — fact(4) pas cu pas

Fiecare apel primește un CADRU pe stivă (ții minte stiva din clasa a IX-a? LIFO!). Coborâm până la bază, apoi rezultatele urcă înapoi.

1int fact(int n) {

2 if (n == 1) return 1; // caz de bază

3 return n * fact(n - 1); // caz general

apasă Pas — pornim cu apelul fact(4) 👆

stiva de apeluri (crește în sus)

Citirea rezultatului: coborârea pune întrebările (fact(4)? → fact(3)? → …), urcarea dă răspunsurile (1 → 2 → 6 → 24). Rezultatul final iese din PRIMUL cadru — ultimul care se închide.

Șabloanele de BAC

Aceleași probleme pe care le-ai rezolvat iterativ în clasa a IX-a (M03!) — acum în haina recursivă cerută la examen.

suma cifrelor

Baza: numărul cu O cifră. Pasul: ultima cifră + suma restului.

1int sc(int n) {

2 if (n < 10) return n;

3 return n % 10 + sc(n / 10);

cmmdc — Euclid recursiv

Algoritmul din M03 (IX), scris în trei rânduri. Perla recursivității.

1int cmmdc(int a, int b) {

2 if (b == 0) return a;

3 return cmmdc(b, a % b);

puterea a^n

Baza: a⁰ = 1. Pasul: a · a^(n−1).

1int put(int a, int n) {

2 if (n == 0) return 1;

3 return a * put(a, n - 1);

numărul de cifre

Aceeași schemă ca suma — schimbi doar ce combini la întoarcere.

1int nc(int n) {

2 if (n < 10) return 1;

3 return 1 + nc(n / 10);

Trucul de citire la BAC: când primești o funcție recursivă necunoscută, NU o „rula" mental la infinit — fă TABELUL apelurilor pe hârtie, exact ca stiva din secțiunea 2: coloana „apel", coloana „ce returnează". De jos în sus.

Pericolele: stiva plină și explozia de apeluri

Recursivitatea e elegantă, dar are două moduri celebre de a da greș.

① Fără caz de bază → Stack Overflow

1int f(int n) {

2 return n * f(n - 1); // n scade… dar NIMIC nu-l oprește!

Fiecare apel mai pune un cadru pe stivă; stiva are limită (câteva mii de cadre) → programul crapă cu Stack Overflow. Prima verificare la orice recursivă: „unde e cazul de bază? se ajunge SIGUR la el?"

② Fibonacci naiv — apelurile se dublează

1int fib(int n) {

2 if (n <= 2) return 1;

3 return fib(n-1) + fib(n-2);

4} // DOUĂ apeluri pe nivel!

n =

Îți amintești șirul lui Fibonacci generat ITERATIV în clasa a IX-a (M07) — n pași, gata. Recursiv naiv, același fib recalculează aceleași valori de mii de ori. Morala: recursivitatea e o UNEALTĂ, nu mereu cea potrivită.

Recursiv sau iterativ?

Criteriu	Iterativ (buclă)	Recursiv
memorie	constantă	un cadru pe apel (stiva!)
cod	uneori mai lung	scurt, oglindește definiția matematică
când strălucește	parcurgeri simple	probleme auto-similare: Divide et impera (Modulul 11!)

Fișa de sinteză

Recursivitatea, condensată.

Definiția: funcția care se apelează pe sine, reducând problema la aceeași problemă, mai mică.

Regulile de aur: ① caz de bază (răspuns direct) · ② caz general care se APROPIE strict de bază.

Stiva de apeluri: fiecare apel = un cadru (LIFO); coborâre cu întrebări, urcare cu răspunsuri.

Șabloane BAC: fact(n)=n·fact(n−1) · sc(n)=n%10+sc(n/10) · cmmdc(a,b)=cmmdc(b,a%b) · put(a,n)=a·put(a,n−1).

Pericole: fără caz de bază → Stack Overflow · fib naiv → explozie exponențială de apeluri.

La BAC: tabelul apelurilor pe hârtie, de jos în sus — nu „rula" mental la infinit.

Exersează: pe pbinfo.ro, categoria „Recursivitate" — și reia subiectele de BAC: aproape fiecare variantă are o funcție recursivă de urmărit.

Funcția care se cheamă pe sine