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

- Count the number of expressions containing n pairs of parentheses which are correctly matched. For n = 3, possible expressions are ((())), ()(()), ()()(), (())(), (()()).
- Count the number of possible Binary Search Trees with n keys.
- Count the number of full binary trees. A rooted binary tree is full if every vertex has either two children or no children) with n+1 leaves.
- Given a number n, return the number of ways you can draw n chords in a circle with 2 x n points such that no 2 chords intersect.

**Recursive Solution**

Catalan numbers satisfy the following recursive formula.

Following is the implementation of above recursive formula.

`#include <iostream>`

`using`

`namespace`

`std;`

`// A recursive function to find nth catalan number`

`unsigned `

`long`

`int`

`catalan(unsigned `

`int`

`n)`

`{`

`` `// Base case`

`` `if`

`(n <= 1)`

`` `return`

`1;`

`` `// catalan(n) is sum of`

`` `// catalan(i)*catalan(n-i-1)`

`` `unsigned `

`long`

`int`

`res = 0;`

`` `for`

`(`

`int`

`i = 0; i < n; i++)`

`` `res += catalan(i)`

`` `* catalan(n - i - 1);`

`` `return`

`res;`

`}`

`// Driver code`

`int`

`main()`

`{`

`` `for`

`(`

`int`

`i = 0; i < 10; i++)`

`` `cout << catalan(i) << `

`" "`

`;`

`` `return`

`0;`

`}`

**Output**

1 1 2 5 14 42 132 429 1430 4862

**Time complexity** of above implementation is equivalent to nth catalan number.

The value of nth catalan number is exponential that makes the time complexity exponential.

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

`#include <iostream>`

`using`

`namespace`

`std;`

`// A dynamic programming based function to find nth`

`// Catalan number`

`unsigned `

`long`

`int`

`catalanDP(unsigned `

`int`

`n)`

`{`

`` `// Table to store results of subproblems`

`` `unsigned `

`long`

`int`

`catalan[n + 1];`

`` `// Initialize first two values in table`

`` `catalan[0] = catalan[1] = 1;`

`` `// Fill entries in catalan[] using recursive formula`

`` `for`

`(`

`int`

`i = 2; i <= n; i++) {`

`` `catalan[i] = 0;`

`` `for`

`(`

`int`

`j = 0; j < i; j++)`

`` `catalan[i] += catalan[j] * catalan[i - j - 1];`

`` `}`

`` `// Return last entry`

`` `return`

`catalan[n];`

`}`

`// Driver code`

`int`

`main()`

`{`

`` `for`

`(`

`int`

`i = 0; i < 10; i++)`

`` `cout << catalanDP(i) << `

`" "`

`;`

`` `return`

`0;`

`}`

**Output**

1 1 2 5 14 42 132 429 1430 4862

**Time Complexity:** Time complexity of above implementation is O(n2)