I have a program I need to do for practice in Java Netbeans for Recursion and Dy
ID: 3688064 • Letter: I
Question
I have a program I need to do for practice in Java Netbeans for Recursion and Dynamic Programming. The program is as follows:
Write a program that uses recursive methods to compute and output the nth term of the Fibonacci series, with n being input by the user. The program should repeatedly ask the user the term number to be computed, and produce two lines of output per term each containing the term number, followed by the term’s value, followed by the number of times the recursive method is invoked to calculate the term's value.
The first line of output will be computed using a dynamic recursive method, and the second line of output will be computed using a recursive method that utilizes non-dynamic programming to reduce the execution time of the program. Be sure the dynamic version of the method executes in under 0.1 seconds for values of n > 45.
Hint: the computed and returned values should be of type long, because the computed values become too large for type int.
Thank you for your help!
Explanation / Answer
public class Fibonacci {
public static void main(String[] args) {
new Fibonacci().test();
}
public void test() {
run(() -> {
long fib1 = fibonacciIterative(45);
System.out.println("Iteratively : Fibonacci of 45 is " + fib1);
});
run(() -> {
long fib2 = fibonacciRecursively(45);
System.out.println("Recursively : Fibonacci of 45 is " + fib2);
});
run(() -> {
long fib3 = fibonacciDynamic(45);
System.out.println("Dynamic : Fibonacci of 45 is " + fib3);
});
}
/*
* Returns: Nth element offibonacci series using iterative method
* complexity: O(n)
*/
public long fibonacciIterative(int N) {
int a = 0;
int b = 1;
int c = a + b;
for (int i = 2; i < N; i++) {
a = b;
b = c;
c = a + b;
}
return c;
}
public long fibonacciRecursively(int N) {
if (N == 0 || N == 1) {
return N;
}
return fibonacciRecursively(N - 1) + fibonacciRecursively(N - 2);
}
/*
* Return: Nth element of fibonacci series using dynamic programming
*/
public long fibonacciDynamic(int N) {
Long table[] = new Long[N+1]; // using wrapper method so the default value becomes null
table[0] = 0l;
table[1] = 1l;
return fastFib(N, table);
}
private long fastFib(int n, Long[] table) {
if (table[n] != null) {
return table[n];
}
long result = fastFib(n - 1, table) + fastFib(n - 2, table);
table[n] = result;
return result;
}
private void run(Runnable r) {
long startTime = System.currentTimeMillis();
r.run();
long endTime = System.currentTimeMillis();
System.out.println((double) (endTime - startTime)/1000 + " seconds required");
System.out.println("_________________________ ");
}
}
sample output
Iteratively : Fibonacci of 45 is 1134903170
0.0 seconds required
_________________________
Recursively : Fibonacci of 45 is 1134903170
7.014 seconds required
_________________________
Dynamic : Fibonacci of 45 is 1134903170
0.001 seconds required
_________________________
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.