Informatică Programare
Recursivitate in programare exemple
Recursivitatea în programare este o tehnică prin care o funcție se autoapelează pentru a rezolva o problemă mai mică. Ea se bazează pe două componente esențiale: cazul de bază (condiția de oprire) și apelul recursiv (autoapelul).
Exemple clasice de funcții recursive
- Calculul factorialului Factorialul lui n (n!) = n * (n-1)!, cu 0! = 1. În C++: int factorial(int n) { if (n == 0) return 1; else return n * factorial(n-1); }
- Șirul lui Fibonacci Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2), cu Fibonacci(0)=0 și Fibonacci(1)=1. În C++: int fib(int n) { if (n <= 1) return n; else return fib(n-1) + fib(n-2); }
- Suma cifrelor unui număr Suma cifrelor lui n = ultima cifră + suma cifrelor lui n/10. În C++: int sumCifre(int n) { if (n == 0) return 0; else return n % 10 + sumCifre(n / 10); }
Aplicații practice în probleme
- Parcurgerea unui vector Se poate parcurge un vector recursiv: void parcurge(int v[], int n) { if (n > 0) { cout << v[n-1] << ' '; parcurge(v, n-1); } }
- Căutarea binară recursivă Într-un vector sortat, se caută un element prin împărțirea repetată a intervalului. În C++: bool binarySearch(int v[], int st, int dr, int x) { if (st > dr) return false; int mij = (st+dr)/2; if (v[mij] == x) return true; else if (v[mij] > x) return binarySearch(v, st, mij-1, x); else return binarySearch(v, mij+1, dr, x); }
Începe cu probleme simple (factorial, Fibonacci) pentru a înțelege fluxul apelurilor recursive.