Topic
1. Count Digits Recursively2. Reverse Number Recursively3. Check Palindrome Recursively4. Product of Digits Recursively5. GCD Recursively6. Convert Number to Binary Recursively7. Print Digits in Words8. Sum of First N Even Numbers Recursively9. Sum of First N Odd Numbers Recursively10. nCr Recursively (Pascal Formula)

nCr Recursively (Pascal Formula)

Calculate nCr using Pascal triangle formula recursively.

AdvancedPhase 3 - Level 2: Advanced RecursionExample 10 of 10
ncr-recursively-pascal-formula.py
1def ncr(n, r):
2    # Base cases
3    if r == 0 or r == n:
4        return 1
5    if r > n:
6        return 0
7    
8    # Recursive case (Pascal's formula)
9    return ncr(n - 1, r - 1) + ncr(n - 1, r)
10

11# Test
12n = int(input("Enter n: "))
13r = int(input("Enter r: "))
14result = ncr(n, r)
15print(f"{n}C{r} = {result}")

Output

Enter n: 5
Enter r: 2
5C2 = 10

What's going on

Pascal's formula: nCr = (n-1)C(r-1) + (n-1)Cr.

Key Concepts:

Base cases: nC0 = nCn = 1
Recursive: sum of two combinations
Uses Pascal triangle property

🔗Related Content

PreviousSum of First N Odd Numbers Recursively