Logic Building/Phase 3 - Level 2: Advanced Recursion/Program

nCr Recursively (Pascal Formula)

Calculate nCr using Pascal triangle formula recursively.

Logic BuildingAdvanced

Logic Building

def ncr(n, r):
    # Base cases
    if r == 0 or r == n:
        return 1
    if r > n:
        return 0
    
    # Recursive case (Pascal's formula)
    return ncr(n - 1, r - 1) + ncr(n - 1, r)

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

Output

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

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

Sum of First N Odd Numbers Recursively