Informatică Programare
Exercitii recursivitate C++ rezolvate bac
Exercițiile de recursivitate pentru bacalaureat în C++ implică probleme tipice cum ar fi calculul factorial, Fibonacci, sau parcurgerea șirurilor. Rezolvarea lor necesită identificarea cazului de bază și a relației recursive.
Probleme frecvente la bac
- Calcul Fibonacci fib(n) = fib(n-1) + fib(n-2), cu fib(0)=0, fib(1)=1. Exemplu: fib(5) = 5.
- Suma cifrelor unui număr sumaCifre(n) = n % 10 + sumaCifre(n/10), cu oprirea când n==0. Exemplu: sumaCifre(123) = 6.
- Inversarea unui șir inverseaza(sir, start, end) schimbă caracterele și autoapelează pentru start+1, end-1, oprire când start >= end.
Rezolvare pas cu pas: Fibonacci
- 1 Pasul 1: Definire funcție int fib(int n) { if (n <= 1) return n; else return fib(n-1) + fib(n-2); }
- 2 Pasul 2: Calcul pentru n=4 fib(4) = fib(3) + fib(2) = (fib(2) + fib(1)) + (fib(1) + fib(0)) = ((fib(1) + fib(0)) + 1) + (1 + 0) = (1 + 0 + 1) + 1 = 3.
- 3 Pasul 3: Optimizare Această implementare este ineficientă din cauza apelurilor duplicate; pentru bac, atenție la complexitate.
Rezolvă manual apelurile recursive pentru suma cifrelor lui 456 pentru a înțelege fluxul.