Catalan Numbers
Generate Catalan numbers with a recursive recurrence. Students trace products of smaller counts and recognize repeated work before trying large term counts.
1# Helper function2def catalan(n):3 if n == 0:4 return 15 result = 06 for i in range(n):7 result += catalan(i) * catalan(n - 1 - i)8 return result910# Take n11n = int(input("Enter n: "))1213# Print Catalan numbers14print(f"First {n} Catalan numbers:")15for i in range(n):16 print(catalan(i), end=" ")17print()
Output
Enter n: 10 First 10 Catalan numbers: 1 1 2 5 14 42 132 429 1430 4862
In this one
- Use a Catalan recurrence
- Multiply split counts
- Recognize uncached recursion
How it works
- 1
Return one for catalan(0).
- 2
For other indexes, add products for every split.
- 3
Print catalan(i) for each requested sequence position.
Edge cases
Why is catalan(0) one?
Why is catalan(0) one?
It is the recurrence's base count for an empty structure.
Does n = 0 print a number?
Does n = 0 print a number?
No. It asks for zero terms.
What's going on
catalan(0) returns one. For larger n, the loop adds catalan(i) * catalan(n - 1 - i) for every split position.
The outer print loop requests indexes zero through n - 1, giving 1, 1, 2, 5 for four terms. Python's call stack holds unfinished products and sums. Many calls recompute the same values, so this direct recurrence is only practical for small examples.
Why is catalan(0) one? It is the recurrence's base count for an empty structure.
Does n = 0 print a number? No. It asks for zero terms.
Quiz
Tap an option. The answer stays hidden until you pick.
Question 1
Why is this slow for large n?
Pick an answer to check it.
Question 2
Why is catalan(0) one?
Pick an answer to check it.
Questions people ask
Why is catalan(0) one?
It is the recurrence's base count for an empty structure.
Does n = 0 print a number?
No. It asks for zero terms.
Why is this slow for large n?
Repeated recursive subproblems are not cached.
๐Related Content
- ๐
Phase 6 - Learn Concepts
Review Phase 6 concepts and explanations
- ๐
Phase 6 - Quiz
Test your Phase 6 understanding with quiz questions
- ๐ป
Phase 6 - All Practice Problems
Explore all practice problems for Phase 6
- ๐
Master Your Logic Building - Complete Course
Browse all phases and tutorials
- ๐ง
Logic Building Overview
Learn about the complete logic building curriculum