# C/C++ 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 ((())), ()(()), ()()(), (())(), (()()).

**C Foundation Course**and master the C language from basic to advanced level. Wait no more, start learning today!

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

## C++

`#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 program to test above function` `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

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

## C++

`#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 program to test above function` `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

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