SHARE
SPREAD
HELP

The Tradition of Sharing

Help your friends and juniors by posting answers to the questions that you know. Also post questions that are not available.


To start with, Sr2Jr’s first step is to reduce the expenses related to education. To achieve this goal Sr2Jr organized the textbook’s question and answers. Sr2Jr is community based and need your support to fill the question and answers. The question and answers posted will be available free of cost to all.

 

#
Authors:
Walter Savitch ,kenrick Mock
Chapter:
Recursion
Exercise:
Programming Projects
Question:2 | ISBN:9780132846813 | Edition: 5

Question

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.

TextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbook

Answer

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:

0 0

Discussions

Post the discussion to improve the above solution.