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

Catalan Numbers

Generate Catalan numbers with a recursive recurrence. Students trace products of smaller counts and recognize repeated work before trying large term counts.

AdvancedPhase 6 - Category 4: Mathematical CombinationsExample 7 of 10
catalan-numbers.py
1# Helper function
2def catalan(n):
3 if n == 0:
4 return 1
5 result = 0
6 for i in range(n):
7 result += catalan(i) * catalan(n - 1 - i)
8 return result
9
10# Take n
11n = int(input("Enter n: "))
12
13# Print Catalan numbers
14print(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. 1

    Return one for catalan(0).

  2. 2

    For other indexes, add products for every split.

  3. 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.