Write a program that uses recursive methods to compute and output the nth term o

Question

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.

package lijp5;

public class Lijp5 {

public static void main(String[] args) {
new Lijp5().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("_________________________ ");
}

}

how would I make this so user can enter their own Nth value.

Explanation / Answer

package lijp;

import static java.lang.System.exit;
import javax.swing.JOptionPane;

public class Lijp5 {
  
public Lijp5(){
//new Lijp5().test();
boolean nextNumber = true;
String readValue;
int value;
while(nextNumber){
readValue = JOptionPane.showInputDialog("Enter the +ve term number for Fibonaaci (0 to stop):");
readValue = readValue.trim();
try{
value = Integer.parseInt(readValue);
if(value > 0){
test(value);
}
else{
exit(0);
}
}
catch(Exception e){
JOptionPane.showMessageDialog(null, e.getMessage() +" it cannot be processed; Try with a +ve integer.");
}
}
}
public static void main(String[] args) {
Lijp5 lijp5 = new Lijp5();   
}
public void test(int value) {
long startTime = System.currentTimeMillis();
long fib1 = fibonacciIterative(value);
long endTime = System.currentTimeMillis();
System.out.println("Iteratively : Fibonacci of " + value + " is " + fib1);
System.out.println((double) (endTime - startTime)/1000 + " seconds required");
System.out.println("_________________________ ");

startTime = System.currentTimeMillis();
long fib2 = fibonacciRecursively(value);
endTime = System.currentTimeMillis();
System.out.println("Recursively : Fibonacci of " + value + " is " + fib2);
System.out.println((double) (endTime - startTime)/1000 + " seconds required");
System.out.println("_________________________ ");

startTime = System.currentTimeMillis();
long fib3 = fibonacciDynamic(value);
endTime = System.currentTimeMillis();
System.out.println("Dynamic : Fibonacci of " + value + " is " + fib3);
System.out.println((double) (endTime - startTime)/1000 + " seconds required");
System.out.println("_________________________ ");
  
}
/*
* Returns: Nth element offibonacci series using iterative method
* complexity: O(n)
*/
public long fibonacciIterative(int N) {
long a = 0;
long b = 1;
long 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;
}
  
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.