Program for nth Catalan Number using Recursion
Catalan numbers satisfy the following recursive formula:
Step-by-step approach:
- Base condition for the recursive approach, when n <= 1, return 1
- Iterate from i = 0 to i < n
- Make a recursive call catalan(i) and catalan(n – i – 1) and keep adding the product of both into res.
- Return the res.
Following is the implementation of the 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 code int main() { for ( int i = 0; i < 10; i++) cout << catalan(i) << " " ; return 0; } |
Java
import java.io.*; 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; } // Driver Code public static void main(String[] args) { CatalnNumber cn = new CatalnNumber(); for ( int i = 0 ; i < 10 ; i++) { System.out.print(cn.catalan(i) + " " ); } } } |
Python3
# A recursive function to # find nth catalan number def catalan(n): # Base Case if n < = 1 : return 1 # Catalan(n) is the sum # of catalan(i)*catalan(n-i-1) res = 0 for i in range (n): res + = catalan(i) * catalan(n - i - 1 ) return res # Driver Code for i in range ( 10 ): print (catalan(i), end = " " ) # This code is contributed by # Nikhil Kumar Singh (nickzuck_007) |
C#
// A recursive C# program to find // nth catalan number using System; class GFG { // A recursive function to find // nth catalan number static 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; } // Driver Code public static void Main() { for ( int i = 0; i < 10; i++) Console.Write(catalan(i) + " " ); } } // This code is contributed by // nitin mittal. |
Javascript
<script> // Javascript Program for nth // Catalan Number // A recursive function to // find nth catalan number function catalan(n) { // Base case if (n <= 1) return 1; // catalan(n) is sum of // catalan(i)*catalan(n-i-1) let res = 0; for (let i = 0; i < n; i++) res += catalan(i) * catalan(n - i - 1); return res; } // Driver Code for (let i = 0; i < 10; i++) document.write(catalan(i) + " " ); // This code is contributed _saurabh_jaiswal </script> |
PHP
<?php // PHP Program for nth // Catalan Number // A recursive function to // find nth catalan number function catalan( $n ) { // Base case if ( $n <= 1) return 1; // catalan(n) is sum of // catalan(i)*catalan(n-i-1) $res = 0; for ( $i = 0; $i < $n ; $i ++) $res += catalan( $i ) * catalan( $n - $i - 1); return $res ; } // Driver Code for ( $i = 0; $i < 10; $i ++) echo catalan( $i ), " " ; // This code is contributed aj_36 ?> |
Output
1 1 2 5 14 42 132 429 1430 4862
Time Complexity: The above implementation is equivalent to nth Catalan number.
The value of nth Catalan number is exponential which makes the time complexity exponential.
Auxiliary Space: O(n)
Program for nth Catalan Number
Catalan numbers are defined as a mathematical sequence that consists of positive integers, which can be used to find the number of possibilities of various combinations.
The nth term in the sequence denoted Cn, is found in the following formula:
The first few Catalan numbers for n = 0, 1, 2, 3, … are : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …
Catalan numbers occur in many interesting counting problems like the following.
- Count the number of expressions containing n pairs of parentheses that are correctly matched. For n = 3, possible expressions are ((())), ()(()), ()()(), (())(), (()()).
- Count the number of possible Binary Search Trees with n keys (See this)
- 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.
See this for more applications.
Examples:
Input: n = 6
Output: 132Input: n = 8
Output: 1430
Contact Us