Question

Design in java a multiple recursive version of Tetranacci calculators. You will calculate Tetranacci(5), Tetranacci(10) and measure the corresponding run times. (for instance, Tetranacci(10) returns 56). You can use Java’s built-in time function for finding the execution time.

Answer 1

Write following program in file Main.java

/*
multiple recursive version of Tetranacci calculators
The tetranacci numbers are a generalization of the Fibonacci numbers defined by the recurrence relation
T(n) = T(n-1) + T(n-2) + T(n-3) + T(n-4)

First few numbers are The first few Tetranacci numbers are:
0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, …
So the base values of first 4 terms are T(1) = T(1) = T(2) = 0, T(3) = 2

*/

//Declare class
class TetranciiRecursive {
// find the nth term using recursive approach
public static int tetranacci(int n) {
// base cases
if (n == 0 || n == 1 || n == 2)
return 0;
// base case
if (n == 3)
return 1;
else
return tetranacci(n - 1) +
tetranacci(n - 2) +
tetranacci(n - 3) +
tetranacci(n - 4);
}
}

public class Main {
public static void main(String[] args) {
long startTime, endTime, totalTime;
//start the time
startTime = System.nanoTime();
System.out.println("Tetranacci(5) = " + TetranciiRecursive.tetranacci(5));
//end time
endTime = System.nanoTime();
//total time
totalTime = endTime - startTime;
//display total execution time of the recursive function
System.out.println("Execution time: " + (totalTime / 10000) + " seconds");
//start the time
startTime = System.nanoTime();
System.out.println("Tetranacci(10) = " + TetranciiRecursive.tetranacci(10));
//end time
endTime = System.nanoTime();
totalTime = endTime - startTime;
//display the time
System.out.println("Execution time: " + (totalTime / 10000) + " seconds");

}
}

Compile the java file and run it. to get the output as below

Tetranacci(5) = 2
Execution time: 4634 seconds   
Tetranacci(10) = 56
Execution time: 53 seconds