Informatică Programare
Exercitii rezolvate functii recursive
Exercițiile rezolvate cu funcții recursive implică funcții care se autoapelează pentru a rezolva probleme repetitive. O problemă clasică este calculul factorialului, unde n! = n * (n-1)! pentru n>0, cu cazul de bază 0! = 1.
Exemple de exerciții rezolvate
- Factorialul unui număr Definim funcția factorial(n): dacă n==0 returnează 1, altfel returnează n * factorial(n-1). Pentru n=5, factorial(5)=5*4*3*2*1=120.
- Șirul Fibonacci Funcția fib(n): dacă n<=1 returnează n, altfel returnează fib(n-1) + fib(n-2). Pentru n=6, fib(6)=fib(5)+fib(4)=5+3=8.
- Suma cifrelor unui număr Funcția suma_cifre(n): dacă n==0 returnează 0, altfel returnează n%10 + suma_cifre(n//10). Pentru n=123, suma_cifre(123)=3+suma_cifre(12)=3+2+1=6.
Pași pentru a scrie o funcție recursivă
- 1 Definește cazul de bază Stabilește condiția care oprește recursivitatea, de exemplu pentru factorial, cazul de bază este n==0.
- 2 Scrie pasul recursiv Exprimă problema în termeni mai simpli, cum ar fi factorial(n) = n * factorial(n-1).
- 3 Testează cu valori mici Verifică funcția pentru input-uri mici pentru a evita bucle infinite, de exemplu testează factorial(3).
Exersează recursivitatea pe probleme simple înainte de a trece la cele complexe, pentru a înțelege fluxul de execuție.