NEED TO DO IT IN LINEAR RECURSION AND BINARY RECURSION !!! In class, we discusse
ID: 3755470 • Letter: N
Question
NEED TO DO IT IN LINEAR RECURSION AND BINARY RECURSION !!!
In class, we discussed about the two versions of Fibonacci number calculations: BinaryFib(n) and LinearFibonacci(n) (refer to your slides and the text book). The first algorithm has exponential time complexity, while the second one is linear. a) In this programming assignment, you will design an algorithm (in pseudo code), and implement (in Java), two recursive versions of an Oddonacci calculator (similar to the ones of Fibonacci) and experimentally compare their runtime performances. Oddonacci numbers are inspired by Fibonacci numbers but start with three predetermined values, each value afterwards being the sum of the preceding three values.
The first few Oddonacci numbers are: 1, 1, 1, 3, 5, 9, 17, 31, 57, 105, 193, 355, 653, 1201, 2209, 4063, 7473, 13745, 25281, 46499, ... For that, with each implemented version you will calculate Oddonacci(5), Oddonacci (10), etc. in increments of 5 up to Oddonacci(100) (or higher value if required for your timing measurement) and measure the corresponding run times. For instance, Oddonacci(10) returns 105 as value.
You can use Java’s built-in time function for this purpose. You should redirect the output of each program to an out.txt file. You should write about your observations on the timing measurements in a separate text file. You are required to submit the two fully commented Java source files, the compiled files, and the text files.
b) Briefly explain why the first algorithm is of exponential complexity and the second one is linear (more specifically, how the second algorithm resolves some specific bottleneck(s) of the first algorithm). You can write your answer in a separate file and submit it together with the other submissions.
c) Do any of the previous two algorithms use tail recursion? Why or why not? Explain your answer. If your answer is “No” then: Can a tail-recursive version of Oddonacci calculator be designed? i. If yes; write the corresponding pseudo code for that tail recursion algorithm and implement it in Java and repeat the same experiments as in part (a) above. ii. If no, explain clearly why such tail-recursive algorithm is infeasible. You will need to submit both the pseudo code and the Java program, together with your experimental results. Keep in mind that Java code is not pseudo code. See full details of submission details below.
Explanation / Answer
Done part a,b, c partial. There are lot of things to be done so part c is not done fully. Please go through the part a & b and if yu have doubt leave a comment.
part b)
Binary version is very slow as it calls oddonacci_binary(9)
it will call: , oddonacci_binary(8) and fib(7). Fib(8) then for each one of them call oddonacci_binary in loop . WHich makes it very slow and code is being called repeatedly many times(about 85 times for oddonacci_binary(9).
This problem can be solved by Linear version which takes n loops if the number of elements are n. So O(n) it takes.
oddonacci_Linear(9) will call oddonacci_Linear() recursively only 7 times.
oddonacci_Linear(9), oddonacci_Linear(8),oddonacci_Linear(7),oddonacci_Linear(6)
oddonacci_Linear(5),oddonacci_Linear(4),oddonacci_Linear(3)
So you can see there is a major difference between two versions.
part c): Oddonacci can be done in tail recursive version also. It is also included in the code below.
part a)
/////////////////////////////////////OddonocciSeries.java////////////////////////////////////////////////////////////
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Scanner;
public class OddonacciSeries {
private static int totalNumbers = 0;
public static int[] array = { 1, 1, 1 };
// TODO: Please check your path
private static String resultsFile = "c:\src\com\java\general\out.txt";
private static String executionTimeFile = "c:\src\com\java\general\excTime.txt";
public static void main(String[] args) {
long startTime, endTime;
int result;
int[] linear_numbers;
createOutputFile(resultsFile);
createOutputFile(executionTimeFile);
System.out.println("Please enter how many numbers are in the series?");
Scanner sc = new Scanner(System.in);
totalNumbers = sc.nextInt();
// Linear Oddonacci Recursion. takes Linear time
startTime = System.currentTimeMillis();
linear_numbers = oddonacci_Linear(totalNumbers);
endTime = System.currentTimeMillis();
writeToFile(resultsFile, "Linear Recursion result= " + linear_numbers[2]);
writeToFile(executionTimeFile,
"Linear Recursion execution time:: " + (endTime - startTime) + " Milliseconds");
// Oddonacci Binary Recursion. Takes exponental time
startTime = System.currentTimeMillis();
result = oddonacci_binary(totalNumbers);
endTime = System.currentTimeMillis();
writeToFile(resultsFile, "Binary Recursion result= " + result);
writeToFile(executionTimeFile,
"Binary Recursion execution time:: " + (endTime - startTime) + " Milliseconds");
// Tail_Linear Oddonacci Recursion much faster than binary
startTime = System.currentTimeMillis();
linear_numbers = oddonacci_tailLinear(totalNumbers);
endTime = System.currentTimeMillis();
writeToFile(resultsFile, "Tail Linear Recursion result= " + linear_numbers[2]);
writeToFile(executionTimeFile,
"Tail Linear Recursion execution time:: " + (endTime - startTime) + " Milliseconds");
sc.close();
System.out.println("Done!!");
}
/**
* Calculate the oddonacci recursively
*
* @param n
* max length of the series
* @return The oddonacci value
*/
public static int oddonacci_binary(int n) {
if (n <= 3) {
return 1;
}
return oddonacci_binary(n - 1) + oddonacci_binary(n - 2) + oddonacci_binary(n - 3);
}
/**
* This tail linear recursion invokes itself once as the very last statement.
*
* @param length_num total length of element in series.
* @return An array third position is the result
*/
public static int[] oddonacci_tailLinear(int length_num) {
if (length_num <= 3)
return array;
int temp = array[0];
array[0] = array[1];
array[1] = array[2];
array[2] = temp + array[0] + array[1];
return oddonacci_tailLinear(length_num - 1);
}
/**
* This linear recursion invokes itself once.
*
* @param length_num total length of element in series.
* @return Array with 3rd position of array is the result.
*/
public static int[] oddonacci_Linear(int length_num) {
int temp;
int[] inputArr;
if (length_num <= 3) {// return initial array with 1,1,1
return new int[] { 1, 1, 1 };
}
// recursive call
inputArr = oddonacci_Linear(length_num - 1);
temp = inputArr[0];
inputArr[0] = inputArr[1];
inputArr[1] = inputArr[2];
inputArr[2] = temp + inputArr[0] + inputArr[1];
return inputArr;
}
private static void createOutputFile(String outputFileName) {
File resultsFile = new File(outputFileName);
// If already exists delete and create a new
if (resultsFile.exists()) {
resultsFile.delete();
try {
resultsFile.createNewFile();
} catch (IOException e) {
System.out.println("Output file not found" + e.getMessage());
}
}
}
// write to the output file
private static void writeToFile(String outputFileName, String str) {
BufferedWriter out = null;
try {
out = new BufferedWriter(new FileWriter(outputFileName, true));
out.write(str + " ");
} catch (IOException e1) {
System.out.println("Writting to file failed." + e1.getMessage());
} finally {
try {
// close outputBuffer
out.close();
} catch (IOException e) {
System.out.println("Output buffer can't close." + e.getMessage());
}
}
}
}
////////////////////////ENd OddonacciSeries.java///////////////////////////////////////////////////
Output Resulting files for 9 numbers
execTime.txt:
Linear Recursion execution time:: 0 Milliseconds
Binary Recursion execution time:: 2 Milliseconds
Tail Linear Recursion execution time:: 0 Milliseconds
////////////////////////////////End
///////////////////out.txt///////////////////
Linear Recursion result= 57
Binary Recursion result= 57
Tail Linear Recursion result= 57
////////////////End out.txt/////////
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.