Calculating binomial coefficient using recursion in C++

In this tutorial, we will learn about calculating the binomial coefficient using a recursive function in C++. Firstly, you must know the use of binomial coefficient calculation. So, the binomial theorem is mostly used in probability theory, for weather forecasting, for complex mathematical calculations, etc. You will learn about the binomial coefficient, calculations and a recursive program to calculate the same.

Binomial coefficient

  • The coefficient is denoted as C(n,r) and also as nCr.
  • It is the coefficient of (x^r) in the expansion of (1+x)^n.
  • It also gives the number of ways the r object can be chosen from n objects.

C(n,r) = n!/r!(n-r)!       where n>=r

Recursive logic to calculate the coefficient in C++

There is also a way to calculate the binomial coefficient using a recursive function call in C++. So let’s derive the generalized formula for recursive function implementation.

C(n,r) = n!/r!(n-r)!
C(n,r) = n(n-1)!/r!(n-r)!
Now, adding and subtracting term – r(n-1)!/r!(n-r)!
C(n,r) = n(n-1)!/r!(n-r)! – (n-1)!/r!(n-r)! + r(n-1)!/r!(n-r)!
C(n,r) = (n-r)(n-1)!/r!(n-r)! + r(n-1)!/r!(n-r)!
C(n,r) = (n-r)(n-1)!/r!(n-r)(n-r-1)! + r(n-1)!/r(r-1)!(n-r)!
C(n,r) = (n-1)!/r!(n-r-1)! + (n-1)!/(r-1)!(n-r)!
C(n,r) = C(n-1,r) + C(n-1,r-1)

So, the generalised formula for calculating binomial coefficient using recurcive function in C++ is –

C(n,r) = C(n-1,r) + C(n-1,r-1)

Apart from this, if the value of n or r is zero then,

C(0,0) = C(n,0) = C(0,r) = C(n,n) = 1

C++ program to calculate binomial coefficient using recursion

To develop a C++ program for calculation of coefficient using recursion, firstly we need to define a recursive function. Firstly, the main() function takes value of n and r from user. Then finally it makes a call to recursive function binomial() which returns the final result. The function binomial calls itself repeatedly and returns the result to the calling funtion i.e. main() function. For doing the same operation number of times, we use do-while loop in our program code.

#include<iostream>
using namespace std;
int binomial(int,int);
int main()
{
	int n,r,result;
	char choice='y';
	do
	{
		cout<<"\n\nENTER VALUE OF n : ";
		cin>>n;
		cout<<"ENTER VALUE OF r : ";
		cin>>r;
		result=binomial(n,r);
		cout<<"BINOMIAL COEFFICIENT - C("<<n<<","<<r<<") IS : "<<result;
		cout<<"\nWANT TO CONTINUE? (y/n) : ";
		cin>>choice;
	}while(choice=='y');
    return 0;
}
int binomial(int n,int r)
{
	if(r==0 || r==n)
		return 1;
	return binomial(n-1,r)+binomial(n-1,r-1);
}

Recursive execution of the function

Obviously, you must know how this function performs the calculation recursively. So let’s take an example of input C(3,2). The function returns the result after calculating as follows.

C(3,2)
     --> C(2,2)         +         C(2,1)
              --> return 1             --> C(1,1)         +         C(1,0)
                                                --> return 1             --> return 1

C(3,2) = 1 + (1 + 1)
C(3,2) = 3

So, in this way, the control passes to function and the result is calculated recursively.

C++ program output

So the output of the above program after execution is –

[email protected]:~/cpp$ g++ binomial.cpp
[email protected]:~/cpp$ ./a.out


ENTER VALUE OF n : 10                                                                                                                         
ENTER VALUE OF r : 2                                                                                                                          
BINOMIAL COEFFICIENT - C(10,2) IS : 45                                                                                                        
WANT TO CONTINUE? (y/n) : y


ENTER VALUE OF n : 5                                                                                                                          
ENTER VALUE OF r : 5                                                                                                                          
BINOMIAL COEFFICIENT - C(5,5) IS : 1                                                                                                          
WANT TO CONTINUE? (y/n) : y


ENTER VALUE OF n : 6                                                                                                                          
ENTER VALUE OF r : 2                                                                                                                          
BINOMIAL COEFFICIENT - C(6,2) IS : 15                                                                                                         
WANT TO CONTINUE? (y/n) : y


ENTER VALUE OF n : 0                                                                                                                          
ENTER VALUE OF r : 0                                                                                                                          
BINOMIAL COEFFICIENT - C(0,0) IS : 1                                                                                                          
WANT TO CONTINUE? (y/n) : n        
[email protected]:~/cpp$

You can give input until you want to find the coefficients. It takes input iteratively until the user wants.

Thank you a lot for reading this tutorial. I hope it helped you.

Leave a Reply

Your email address will not be published. Required fields are marked *