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.
1def ncr(n, r):2 # Base cases3 if r == 0 or r == n:4 return 15 if r > n:6 return 078 # Recursive case (Pascal's formula)9 return ncr(n - 1, r - 1) + ncr(n - 1, r)1011# Test12n = 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
Return one for either Pascal edge.
- 2
Return zero when r exceeds n.
- 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).
๐Related Content
- ๐
Phase 3 - Learn Concepts
Review Phase 3 concepts and explanations
- ๐
Phase 3 - Quiz
Test your Phase 3 understanding with quiz questions
- ๐ป
Phase 3 - All Practice Problems
Explore all practice problems for Phase 3
- ๐
Master Your Logic Building - Complete Course
Browse all phases and tutorials
- ๐ง
Logic Building Overview
Learn about the complete logic building curriculum