Recursivitate
Ideile de bază pe scurt și, unde există, exercițiile din subiectele de BAC care le verifică. Lecția completă, animată, cu grile și exerciții corectate, e în aplicația Tomomi.
Pe scurt
Sintaxă: funcția recursivă
Ca orice funcție, plus un apel în propriul corp: cazul de bază răspunde direct, pasul recursiv reduce problema.
int fact(int n) {
if (n == 0) {
return 1; // caz de bază
}
return n * fact(n - 1); // pas recursiv
}Idee: caz de bază + pas recursiv
Cazul de bază oprește lanțul de apeluri cu un răspuns direct; pasul recursiv cheamă funcția pentru o problemă mai mică. Fără cazul de bază, recursivitatea nu se termină.
Șablon: recursia pe cifre
Ultima cifră se desprinde cu n % 10, restul cu n / 10; cazul de bază este n == 0:
int sumcif(int n) {
if (n == 0) {
return 0;
}
return n % 10 + sumcif(n / 10);
}Capcana: cazul de bază care lipsește
O funcție recursivă fără caz de bază cheamă la nesfârșit: fact(0) ar cere fact(-1), apoi fact(-2) și tot așa. Interpretorul oprește lanțul cu o eroare, dar răspunsul nu mai vine. Verifică întâi oprirea, apoi pasul.
Șablon: șirul lui Fibonacci
Fiecare termen adună cei doi termeni dinainte; recurența are DOUĂ cazuri de bază:
int fib(int n) {
if (n <= 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}Idee: arborele repetă subarborii
În varianta recursivă, fib(2) se recalculează în fiecare subarbore care îl cere: de trei ori pentru fib(5). De aceea pentru n mare se folosește o buclă care memorează ultimii doi termeni.
Din subiectele de BAC
Exerciții reale din subiectele anilor trecuți. Încearcă-le singur înainte să deschizi rezolvarea.
Subprogramul f este definit alăturat. Indicați ce se afișează în urma apelului f(3);.
void f(int n)
{ int i;
for(i=1;i<=n;i++)
if(i%2==0)
{ cout<<i;
f(i-1);
}
else
{ f(i-1);
cout<<i;
}
}a. 1211213
b. 123121
c. 123
d. 01201012013
Vezi rezolvarea
Cazul de bază este : bucla for nu se execută niciun pas, deci f(0) nu afișează nimic. Construim de jos în sus:
f(1): impar →f(0)(nimic), apoi1⟹ afișează 1f(2): →1; par →2, apoif(1)=1⟹ afișează 121f(3): →1; →2urmat def(1)=1, deci21; impar →f(2)=121urmat de3, deci1213
Concatenând: 1 + 21 + 1213 = 1211213, litera a.
Metoda de lucru: la recursie cu buclă, nu urmări apelurile în minte - calculează întâi ce afișează f(0), apoi f(1), apoi f(2), și folosește rezultatele deja obținute.
Subprogramul f este definit alăturat. Indicați ce se afișează în urma apelului f(2020,0);.
void f(int x, int y)
{ if (x<10) cout<<x;
else
{ f(x/10,y+1);
cout<<x%10;
}
cout<<y;
}a. 23020
b. 2022100
c. 02023210
d. 23022100
Vezi rezolvarea
Urmărim lanțul de apeluri recursive:
1. f(2020,0): 2020 ≥ 10, deci apelează f(202,1), urmând să afișeze apoi 0 (2020%10) și 0 (y).
2. f(202,1): apelează f(20,2), apoi afișează 2 și 1.
3. f(20,2): apelează f(2,3), apoi afișează 0 și 2.
4. f(2,3): 2 < 10, afișează 2, apoi 3.
La întoarcerea din recursivitate se afișează, în ordine: 2 3 (din f(2,3)), 0 2 (din f(20,2)), 2 1 (din f(202,1)), 0 0 (din f(2020,0)).
Rezultat: 23022100, litera d.
Subprogramul f este definit alăturat. Indicați ce se afișează în urma apelului f(23);.
void f(int n)
{ if(n!=0) f(n/2);
cout<<n%2;
}a. 100111
b. 111010
c. 010111
d. 01251123
Vezi rezolvarea
Apelurile recursive se fac înaintea afișării, deci afișarea are loc la revenirea din recursivitate:
La revenire se afișează, în ordine: , , , , , .
Pe ecran apare 010111, adică reprezentarea binară a lui () precedată de un . Răspunsul corect este c.