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)
3) 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.
The first few Catalan numbers for n = 0, 1, 2, 3, … are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …
Recursive Solution
Following is the implementation of above recursive formula.
[pastacode lang=”java” manual=”class%20CatalnNumber%20%7B%0A%20%0A%20%20%20%20%2F%2F%20A%20recursive%20function%20to%20find%20nth%20catalan%20number%0A%20%0A%20%20%20%20int%20catalan(int%20n)%20%7B%0A%20%20%20%20%20%20%20%20int%20res%20%3D%200%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Base%20case%0A%20%20%20%20%20%20%20%20if%20(n%20%3C%3D%201)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%201%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20n%3B%20i%2B%2B)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20res%20%2B%3D%20catalan(i)%20*%20catalan(n%20-%20i%20-%201)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20return%20res%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20public%20static%20void%20main(String%5B%5D%20args)%20%7B%0A%20%20%20%20%20%20%20%20CatalnNumber%20cn%20%3D%20new%20CatalnNumber()%3B%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%2010%3B%20i%2B%2B)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(cn.catalan(i)%20%2B%20%22%20%22)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%7D” message=”Java Program” highlight=”” provider=”manual”/]
Output :
1 1 2 5 14 42 132 429 1430 4862
[ad type=”banner”]