Given two numbers N and r, find the value of NCr using recursion
Examples:
Input: N = 5, r = 2
Output: 10
Explanation: The value of 5C2 is 10Input: N = 3, r = 1
Output: 3
Approach 1: One very interesting way to find the C(n,r) is the recursive method which is based on the recursive equation.
C(n,r) = C(n-1,r-1) + C(n-1,r)
Below is the implementation of the above approach as follows:
C++
#include <bits/stdc++.h>using namespace std;// Function to calculate the value of nCr// using recursionint comb(int n,int r){ if(n<r){ return 0; } if(r == 0){ return 1; } if(r == 1){ return n; } if(n == 1){ return 1; } return comb(n-1,r-1)+comb(n-1,r);}// Driver codeint main(){ int n = 10,r = 5; cout << comb(n,r);} |
Java
// Java code for the above approachimport java.io.*;class GFG { // Function to calculate the value of nCr // using recursion static int comb(int n, int r) { if(n<r){ return 0; } if(r == 0){ return 1; } if(r == 1){ return n; } if(n == 1){ return 1; } return comb(n-1,r-1)+comb(n-1,r); } public static void main(String[] args) { int n = 5, r = 3; System.out.println(comb(n, r)); }} |
Python3
# Python code to implement above approach# Function to calculate the value of nCr# using recursiondef comb(n, r): if(n < r): return 0 if(r == 0): return 1 if(r == 1): return n if(n == 1): return 1 return comb(n - 1, r - 1) + comb(n - 1, r) # Driver coden = 10r = 5print(comb(n, r))# This code is contributed by Pushpesh Raj. |
C#
using System;public class GFG{ // Function to calculate the value of nCr // using recursion static int comb(int n, int r) { if(n<r){ return 0; } if(r == 0){ return 1; } if(r == 1){ return n; } if(n == 1){ return 1; } return comb(n-1,r-1)+comb(n-1,r); } // Driver code static public void Main (){ int n = 5, r = 3; Console.WriteLine(comb(n, r)); }} |
Javascript
<script>//Javascript code to implement above approach// Function to calculate the value of nCr// using recursionfunction comb(n, r){ if( n<r ){ return 0; } if(r == 0){ return 1; } if(r == 1){ return n; } if(n == 1){ return 1; } return comb(n-1,r-1) + comb(n-1,r);}// Driver codelet n = 5, r = 3;document.write(comb(n,r)); // </script> |
252
Time Complexity: O(2^n), Auxiliary Space: O(n)
Approach 2: Another idea is simply based on the below formula.
NCr = N! / (r! * (N-r)!)
Also,
NCr-1 = N! / ( (r-1)! * (N – (r-1))! )Hence,
- NCr * r! * (N – r)! = NCr-1 * (r-1)! * (N – (r-1))!
- NCr * r * (N-r)! = NCr-1 * (N-r+1)! [eliminating (r – 1)! from both side]
- NCr * r = nCr-1 * (N-r+1)
Therefore,
NCr = NCr-1 * (N-r+1) / r
Below is the implementation of the above approach:
C++
// C++ code to implement above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the value of nCr// using recursionint nCr(int N, int r){ int res = 0; if (r == 0) { return 1; } else { res = nCr(N, r - 1) * (N - r + 1) / r; } return res;}// Driver codeint main(){ int N = 5, r = 3; cout << nCr(N, r); return 0;} |
Java
// Java code for the above approachimport java.io.*;class GFG { // Function to calculate the value of nCr // using recursion static int nCr(int N, int r) { int res = 0; if (r == 0) { return 1; } else { res = nCr(N, r - 1) * (N - r + 1) / r; } return res; } public static void main(String[] args) { int N = 5, r = 3; System.out.println(nCr(N, r)); }}// This code is contributed by Potta Lokesh |
Python3
# Python code to implement above approach# Function to calculate the value Of nCr# using recursiondef nCr(N, r): res = 0 if(r == 0): return 1 else: res = nCr(N, r-1) * (N-r + 1) / r return res# Driver codeif __name__ == "__main__": N = 5 r = 3 print(int(nCr(N, r))) |
C#
using System;public class GFG{ // Function to calculate the value of nCr // using recursion static int nCr(int N, int r) { int res = 0; if (r == 0) { return 1; } else { res = nCr(N, r - 1) * (N - r + 1) / r; } return res; } // Driver code static public void Main (){ int N = 5, r = 3; Console.WriteLine(nCr(N, r)); }}// This code is contributed by hrithikgarg03188. |
Javascript
<script>//Javascript code to implement above approach// Function to calculate the value of nCr// using recursionfunction nCr(N, r){ let res = 0; if (r == 0) { return 1; } else { res = nCr(N, r - 1) * (N - r + 1) / r; } return res;}// Driver codelet N = 5, r = 3;document.write(nCr(N,r)); // This code is contributed by Taranpreet // </script> |
10
Time Complexity: O(r), Auxiliary Space: O(r)
Complexity Analysis:
The time complexity of the above approach is O(r). This is because the function makes a single recursive call for each value of r, and the time taken to calculate the value of nCr is constant.
The Auxiliary space complexity of the above approach is O(r), as the recursive function calls create a new stack frame for each call. This means that the program will consume a significant amount of memory for larger values of r.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
