Lecture 70:- nCr using Recursion

To calculate the combination (nCr) using recursion, you can use the formula: nCr = (n-1)C(r-1) + (n-1)Cr. Here's an example implementation in Python:

pythonCopy code

def nCr(n, r):    # Base cases    if r == 0 or n == r:        return 1    # Recursive case    return nCr(n - 1, r - 1) + nCr(n - 1, r)

Let's break down how the code works:

1. The nCr function takes two parameters: n (the total number of items) and r (the number of items to choose).
2. We define the base cases: if r is 0 or if n is equal to r, then it means either we have to choose 0 items or we have to choose all the items. In both cases, there is only one way to do so, and we return 1.
3. In the recursive case, we use the formula for combinations: nCr = (n-1)C(r-1) + (n-1)Cr. We make two recursive calls to calculate the combinations for choosing r items from n-1 items.
4. We add the results of the recursive calls and return the sum, which represents the total number of combinations (nCr).

Here's an example usage of the nCr function:

pythonCopy code

result = nCr(5, 2) print(result)  # Output: 10 result = nCr(6, 3) print(result)  # Output: 20

In the first example, we calculate the number of combinations for choosing 2 items out of 5 items, which is 10.

In the second example, we calculate the number of combinations for choosing 3 items out of 6 items, which is 20.