Probleme Rezolvate

Scrieţi un subprogram recursiv care să calculeze combinări de n luate câte k — C( n,k ), definite prin funcţiile recursive:
-> C( n,k ) = C(n-1,k)+ C(n-1,k-1), cu C(n,0) = C( n,n ) = 1 şi C(n,1)= n
-> C( n,k ) =((n-k+1) / k)*C(n,k-1), cu C(n,0) = 1
Calculaţi , pentru fiecare dintre subprogramele recursive, adâncimea recursivității pentru C(5,2). Care dintre imp lementări este mai eficientă?

# include < iostream >
using namespace std ;
int combinari_1 ( int n, int k) {
if (k == 0 || k == n) {
return 1 ;
} else if (k == 1 ) {
return n;
}
return combinari_1 (n - 1 , k) + combinari_1 (n - 1 , k - 1 );
}
int combinari_2 ( int n, int k, int depth = 0 ) {
if (k == 0 ) {
return 1 ;
}
return ((n - k + 1 ) / ( double )k) * combinari_2 (n, k - 1 , depth + 1 );
}
int main () {
int n = 5 ;
int k = 2 ;
int result1 = combinari_1 (n, k);
cout << "C(n, k) folosind prima functie recursiva: " << result1 << endl ;
int result2 = combinari_2 (n, k);
cout << "C(n, k) folosind a doua functie recursiva: " << result2 << endl ;
return 0 ;
}

Pentru C(5, 2), adâncimea recursivității este diferită în ambele cazuri:
În acest caz, ambele implementări au aceeași adâncime de recursivitate. Cu toate acestea, a doua implementare este de obicei mai eficientă, deoarece implică un singur apel recursiv în loc de două apeluri recursive în prima implementare. Acest lucru reduce numărul total de apeluri ale funcției și, prin urmare, timpul de execuție al programului.