The formula for computing the number of ways of choosing r different things from a set of n things is the following:
C(n , r) = n! / (r! * (n - r)!)
The factorial function n! is defi ned by
n! = n * (n – 1) * (n – 2) * ... * 1
Discover a recursive version of the formula for C(n , r) and write a recursive function that computes the value of the formula. Embed the function in aprogram and test it.
The following recursive function definition is used to find the number of ways of choosing r different things from a set of n things:
//Function definition of nCr:
//This function accepts two integer variables n and r
int nCr(int n, int r)
{
//Use recursive function to calculate
//the value of the formula n!(factorila of n)
return factNum(n) / (factNum(r) * factNum(n - r));
}
// Function definition of factNum:
//It accepts an integer parameter, n and
//compute the factorial of n
int factNum(int n)
{
int nFactorial = 1;
if(n==0)
return 1;
for (int i = 2; i <= n; i++)
nFactorial = nFactorial * i;
return nFactorial;
}
COMPLETE EXECUTABLE C++ CODE:
//Default header function
#include <iostream>
using namespace std;
//Function prototype
int factNum(int n);
//Function definition of nCr:
//This function accepts two integer variables n and r
int nCr(int n, int r)
{
//Use recursive function to calculate
//the value of the formula n!(factorila of n)
return factNum(n) / (factNum(r) * factNum(n - r));
}
// Function definition of factNum:
//It accepts an integer parameter, n and
//compute the factorial of n
int factNum(int n)
{
int nFactorial = 1;
if(n==0)
return 1;
for (int i = 2; i <= n; i++)
nFactorial = nFactorial * i;
return nFactorial;
}
//Program starts with main method
int main()
{
int n,r;
cout<<"Enter n value:";
cin>>n;
cout<<"Enter r value:";
cin>>r;
//Call the function nCr and
//print result on screen
cout <<"The value of "<<n<<"C"<<r<<" is "<<nCr(n, r);
return 0;
}
OUTPUT OF THE PROGRAM CODE: