Informatică Programare
Ce este recursivitatea in programare C++?
Recursivitatea în C++ este o tehnică de programare în care o funcție se autoapelează pentru a rezolva o problemă prin descompunerea ei în subprobleme mai mici. Funcția recursivă are două componente esențiale: cazul de bază, care oprește apelurile, și cazul recursiv, care reduce problema. De exemplu, calculul factorialului n! = n * (n-1)! cu 0! = 1 ilustrează această abordare.
Componentele unei funcții recursive
- Cazul de bază Condiția care oprește apelurile recursive, prevenind o buclă infinită. Pentru factorial, if(n==0) return 1.
- Cazul recursiv Partea unde funcția se autoapelează cu argumente mai mici. Pentru factorial, return n * factorial(n-1).
- Exemplu simplu int factorial(int n) { if(n==0) return 1; else return n * factorial(n-1); }
Aplicații comune
- Calculul șirului Fibonacci fib(n) = fib(n-1) + fib(n-2), cu fib(0)=0, fib(1)=1.
- Parcurgerea arborilor Folosită în algoritmi pentru explorarea structurilor ierarhice.
- Sortări recursive QuickSort și MergeSort utilizează recursivitatea pentru împărțirea datelor.
Testează întotdeauna cazul de bază pentru a evita depășirea stivei.