The Catalan numbers (C) are given by: C(0) = 1 and C(n) = C(0)C(n-1) + C(1)C(n-2
ID: 3668101 • Letter: T
Question
The Catalan numbers (C) are given by:
C(0) = 1 and
C(n) = C(0)C(n-1) + C(1)C(n-2) + C(2)C(n-3) + … + C(n-3)C(2) + C(n-2)C(1) + C(n-1)C(0)
For example,
C(4) = C(0)C(3) + C(1)C(2) + C(2)C(1) + C(3)C(0) = (15) + (12) + (21) + (51) = 14
The following recursive method can be used to calculate the Catalan numbers:
but as the method name implies, the method is not very efficient and runs pretty slowly.
Can you think of a way to rewrite the method to make it more efficient.
Hint: How many times is each Catalan number being calculated when you ask the method to calculate C(4)? Does it really need to calculate each number multiple times?
Problem 2. How might you modify the method to calculate Fibonacci numbers (Links to an external site.) listed below to make it more efficient -- but still recursive (hint: memoization)?
public class Fibonacci {
public static void main(String[] args){
for(int i = 0; i < 46; i++){
System.out.println("Fibonacci(" + i + ") = "+ fibonacci(i));
}
}
private static int fibonacci(int n){
if(n == 0 || n == 1){
return 1;
} else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
}
Use System.nanoTime() to time your methods.
How long did it take to calculate the first 45 Fibonacci numbers using the original recursive method?
How long did it take using your revised recursive method?
Rewrite the fibonacci(int n) method to calculate the numbers using a loop. Do you prefer the recursive or the iterative solution? Why?
Explanation / Answer
answer 1:
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) + " ");
}
}
}
Time Complexity: Time complexity of above implementation is O(n2)
answer 2: