# Java Program for nth Catalan Number

Catalan numbers are a sequence of natural numbers that occurs in many interesting counting problems like following.

**1)** Count the number of expressions containing n pairs of parentheses which are correctly matched. For n = 3, possible expressions are ((())), ()(()), ()()(), (())(), (()()).

**2)** Count the number of possible Binary Search Trees with n keys (See this)

See this for more applications.

The first few Catalan numbers for n = 0, 1, 2, 3, … are **1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …**

## Recommended: Please solve it on “__PRACTICE__ ” first, before moving on to the solution.

__PRACTICE__**Recursive Solution**

Catalan numbers satisfy the following recursive formula.

Following is the implementation of above recursive formula.

## Java

`class` `CatalnNumber {` ` ` ` ` `// A recursive function to find nth catalan number` ` ` ` ` `int` `catalan(` `int` `n) {` ` ` `int` `res = ` `0` `;` ` ` ` ` `// Base case` ` ` `if` `(n <= ` `1` `) {` ` ` `return` `1` `;` ` ` `}` ` ` `for` `(` `int` `i = ` `0` `; i < n; i++) {` ` ` `res += catalan(i) * catalan(n - i - ` `1` `);` ` ` `}` ` ` `return` `res;` ` ` `}` ` ` ` ` `public` `static` `void` `main(String[] args) {` ` ` `CatalnNumber cn = ` `new` `CatalnNumber();` ` ` `for` `(` `int` `i = ` `0` `; i < ` `10` `; i++) {` ` ` `System.out.print(cn.catalan(i) + ` `" "` `);` ` ` `}` ` ` `}` `}` |

**Output:**

1 1 2 5 14 42 132 429 1430 4862

**Dynamic Programming Solution**

We can observe that the above recursive implementation does a lot of repeated work (we can the same by drawing recursion tree). Since there are overlapping subproblems, we can use dynamic programming for this. Following is a Dynamic programming based implementation in C++.

Please refer complete article on Program for nth Catalan Number for more details!