The classic fibonacci calculation (Chapter 2, Exercise #3) can also be done recursively (code below), but is very slow. Your task: Write a faster version that is still recursive, but far more efficient. Call the new improved method "fibFast" and get the code shown below to work. You should discover that the 45th Fibonacci number (1134903170) takes a long time to calculate with the provided code (like 10 seconds) and the 46th takes even longer. The 47th exceeds the size of allowable primitive int in Java. So we need big changes in this code.

Re-write a better recursive calculation, and use BigInteger from the Java APIhttp://docs.oracle.com/javase/8/docs/api/java/math/BigInteger.html (Links to an external site.) (Links to an external site.)

(this means you should return BigInteger from fibFast method)

Requirements:

fibFast MUST be a recursive method, and/or a fibFast overload helper as recursive.

leave the text fibonacci method in your Fibonacci Class, so the listing below will work.

start with class listing below, and add in fibFast static method (see textbook description, change method name to fibFast).

do NOT add class constants nor globals, as I will test your method with external testing code.

public class Fibonacci { public static void main(String[] args) { int test = 45; System.out.println(fibFast(test)); // a fast recursive version System.out.println(fibonacci(test)); // slow version in text } public static int fibonacci(int n) { if (n<=2) { return 1; } else { return fibonacci(n-1) + fibonacci(n-2); } }

Results:

45th Fibonacci number from fibFast(45) is 1134903170

345th Fibonacci number from fibFast(345) is 563963353180680437428706474693749258212475354428320807161115873039415970