Founding Batch Offer ยท HLD ยท LLD ยท System Design at โ‚น799 until 30 Nov

nCr Recursively (Pascal Formula)

Compute combinations with Pascal's recursive formula. Students trace two smaller subproblems, edge entries equal to one, and repeated work in the call tree.

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

In this one

  • Apply Pascal's identity
  • Handle edge combinations
  • Recognize branching cost

How it works

  1. 1

    Return one for either Pascal edge.

  2. 2

    Return zero when r exceeds n.

  3. 3

    Otherwise add the two smaller combination calls.

Edge cases

What does nC0 return?

What does nC0 return?

One, representing the empty selection.

Are negative n or r supported?

Are negative n or r supported?

No. Those inputs need validation before this recurrence.

What's going on

nCr counts selections where order does not matter. Pascal's identity splits it into choices that include a particular item and choices that exclude it.

The edge cases r equal to zero or n return one. r greater than n returns zero. For valid nonnegative inputs, the two branches shrink n until edges are reached. Python's call stack tracks pending sums; repeated subproblems make large examples expensive.

What does nC0 return? One, representing the empty selection.

Are negative n or r supported? No. Those inputs need validation before this recurrence.

Quiz

Tap an option. The answer stays hidden until you pick.

Question 1

Which results are added?

Pick an answer to check it.

Question 2

What does nC0 return?

Pick an answer to check it.

Questions people ask

What does nC0 return?

One, representing the empty selection.

Are negative n or r supported?

No. Those inputs need validation before this recurrence.

Which results are added?

C(n-1,r-1) and C(n-1,r).