Funcții recursive: cum afli valoarea (doar matematică-informatică)

Pe scurt

2 minesențialul, de recitit oricând

Culorile din lecție:termencifră, datăidee-cheie

• Doar la matematică-informatică. Capitolul 8 din programă nu apare la științele naturii.
• O funcție recursivă se apelează pe sine. Are mereu două părți: o condiție de oprire și un autoapel cu date mai mici.
• În cele 23 de lucrări MI din 2023-2027 din platformă, există câte un item de acest fel în fiecare: de 21 de ori la Subiectul I (4 p), de 2 ori la II.2 (6 p).
• Enunțurile nu folosesc cuvântul „recursiv”. Scrie doar „Subprogramul f este definit alăturat”, iar tu observi că f se apelează pe sine.
• Recursivitatea, backtracking-ul, grafurile și arborii dau împreună 4 itemi în fiecare dintre aceste lucrări, adică 16 sau 18 puncte din cele 90 scrise. Sunt itemi scurți, cu răspuns verificabil.

Urmează · 2 min

Ideea, apoi numele oficial

3 min

Ești la coadă și vrei să știi al câtelea ești. Nu numeri. Îl întrebi pe cel din față, iar el îl întreabă pe cel din fața lui. Primul din coadă nu mai are pe cine să întrebe și spune „1”. Răspunsul se întoarce din om în om, cu 1 în plus de fiecare dată.

Oficial: omul care nu mai întreabă pe nimeni este condiția de oprire. Întrebarea către cel din față este autoapelul. Oamenii care așteaptă răspunsul sunt apelurile neterminate, ținute pe stivă.

int fact(int n)
{ if(n==0) return 1;
  return n*fact(n-1);
}

Apelul fact(3) merge așa:

Fiecare apel are propriile copii ale parametrilor transmiși prin valoare. n din fact(3) nu se schimbă când fact(2) lucrează cu al lui n.

În Pascal, valoarea se atribuie numelui funcției, nu se folosește return: if n=0 then fact:=1 else fact:=n*fact(n-1). Mecanismul este același.

Urmează · 3 min

Metoda de pe foaie

1 min

1. Cobori
   Scrii apelurile unul sub altul, cu parametrii calculați: împărțire întreagă, rest, adunări.
2. Te oprești
   Când condiția de oprire e adevărată, scrii valoarea returnată lângă ultimul apel.
3. Urci
   Înlocuiești rezultatul în apelul de deasupra și calculezi, până la primul apel.
4. Verifici varianta
   La grilă, compară cu cele patru variante abia la final. Variantele greșite sunt rezultatele greșelilor obișnuite.

Urmează · 1 min

Oficial: sesiunea specială 2026, varianta 4, I.2

1 min

Se cere f(1,10).

int f(int n,int m)
{ if(n>=m) return 0;
  else return 1+f(n+1,m-2);
}

Barem: varianta b, adică 3, 4 p. Greșeala tipică este să numeri și ultimul apel: sunt patru apeluri, dar doar trei adunări de 1.

Urmează · 1 min

Oficial: rezervă 2026, varianta 5, I.2

1 min

Se cere f(56579).

int f(int n)
{ if(n==0) return 0;
  if(n%2==1) return f(n/10)+1;
  return f(n/10)-1;
}

n%2 se uită la paritatea numărului, deci la ultima cifră. Funcția parcurge cifrele: +1 pentru impar, -1 pentru par. Cifrele 5, 6, 5, 7, 9 dau 1-1+1+1+1 = 3. Barem: varianta d, 4 p.

Aici nu ai nevoie de toate apelurile scrise. După ce ai văzut ce face funcția, numeri. Dacă ai timp, verifică pe un număr mai scurt.

Urmează · 1 min

Oficial: II.2, cu 6 puncte

3 min

August 2025, varianta 4. Se cer f(3,9) și f(1,1000).

int f(int x,int y)
{ if(x*5>y/5) return x;
  return f(x*5,y/5);
}

• f(3,9): 15 > 1, deci rezultatul e 3.
• f(1,1000): 5 > 200 e fals, trece la f(5,200). 25 > 40 e fals, trece la f(25,40). 125 > 8 e adevărat, deci rezultatul e 25.

Barem: câte 3 p pentru fiecare valoare. Aici nu există nimic de calculat la întoarcere: rezultatul ultimului apel urcă neschimbat.

Rezervă iunie 2025, varianta 7. Se cer f(2) și f(17).

int f(int x)
{ if(x<=4) return x;
  else return x-f(x-2);
}

• f(2) = 2, din condiția de oprire.
• La f(17) cobori din 2 în 2 până la f(3)=3. Urci: f(5)=5-3=2, f(7)=7-2=5, f(9)=9-5=4, f(11)=11-4=7, f(13)=13-7=6, f(15)=15-6=9, f(17)=17-9=8.

Barem: câte 3 p pentru fiecare soluție. Scrie-le ca în barem: f(2)=2, f(17)=8.

Urmează · 3 min

Tipare pe care le recunoști

3 min o întrebare la final

Unele funcții fac ceva cunoscut. Dacă vezi tiparul, ai și o verificare a rezultatului.

La modelul 2026, tabloul este (2,0,2,6,8). Doar pozițiile 3 și 4 au v[d] egal cu 2*d: 6 și 8.

Urmează · 3 min

Când funcția e mai încâlcită

4 min

Simulare 2025, I.2. Care apel dă 2025?

int f(int x)
{ if(x>500) return 5;
  else return 5*f(x*10+5)+x;
}

Încearcă f(0): cobori prin 0, 5, 55, 555. f(555)=5, f(55)=25+55=80, f(5)=400+5=405, f(0)=2025+0=2025. Barem: varianta d. Pentru grile de felul acesta, începe cu varianta care pare cea mai simplă.

Model 2025, I.2. Se cere f(2,5). Autoapelul este în parametrul altui autoapel.

int f(int n,int x)
{ if(n>0)
    return f(f(n-2,x)-2,x-5);
  return x;
}

Calculezi întâi apelul din interior.

Deci f(2,5) = -5. Barem: varianta d.

Model 2027, I.3. Se cere f(97,0).

int f(int n,int k)
{ if(n==0) return 0;
  else if(k*k<=n)
    return k+f(n/2,k+1);
  else return k+f(n/2,n);
}

Perechile (n,k) sunt (97,0), (48,1), (24,2), (12,3), (6,4), (3,6), (1,3), (0,1). Atenție la (6,4): 16 > 6, deci al doilea parametru devine n, adică 6. Se adună valorile lui k până la oprire: 0+1+2+3+4+6+3 = 19. Barem: varianta C.

Urmează · 4 min

Dacă trebuie să scrii una

2 min 2 întrebări la final

În lucrările 2023-2027 nu am găsit niciun item care să ceară explicit un subprogram recursiv, iar la III.1 baremul punctează „orice modalitate de rezolvare corectă”. Programa cere totuși să le știi, și e bine să poți scrie măcar formele scurte:

int sc(int n)
{ if(n==0) return 0;
  return n%10+sc(n/10);
}

int fib(int n)
{ if(n<=2) return 1;
  return fib(n-1)+fib(n-2);
}

int cmmdc(int a,int b)
{ if(b==0) return a;
  return cmmdc(b,a%b);
}

sc(528) e 15, fib(6) e 8, cmmdc(84,36) e 12. Ordinea de scriere e mereu aceeași: întâi oprirea, apoi autoapelul cu date mai mici.

Urmează · 2 min

Ce se cere la BAC

3 mincum apare la examen

Urmează · 3 min

Greșeli care costă puncte

1 mincapcanele de evitat

• Te oprești la condiția de oprire, fără să urci înapoi.
• Împărțire reală în loc de împărțire întreagă: 9/5 este 1, iar 1000/5/5 este 40.
• Greșeli de semn la scădere: x-f(x-2) nu se distribuie din ochi, calculează pas cu pas.
• Numeri apelurile în loc de adunări: patru apeluri înseamnă uneori trei adunări.
• Ignori al doilea parametru, deși el se schimbă, ca la modelul 2027.
• Răspunzi din tipar fără verificare: tiparul te ajută, dar apelul concret decide.

Urmează · 1 min