L12 - Recursion Exercise

Part A – Fibonacci 
 A recursive algorithm can be very fast. Sometimes it's the only solution to a problem. Sometimes the recursive version of an algorithm has very poor performance compared to an iterative solution. In this part of the exercise, we'll empirically determine the performance of a recursive Fibonacci algorithm by measuring the elapsed time required to run the algorithm for a series of values. Fill in the missing code in the fibonacci method in the FibonacciTest class: 
 import java.util.*; 
public class FibonacciTest { 
 public static void main(String[] args) { 
 Scanner myScanner = new Scanner(System.in); 
 boolean done = false;
 while (!done) { 
 System.out.print("Enter an integer or Q to quit: "); 
 String answer = myScanner.nextLine();
 if (answer.equalsIgnoreCase("q")) done = true; 
 else { 
 int myLong = Integer.parseInt(answer); 
 long startTime = System.currentTimeMillis();
 long fibN = fibonacci(myLong); 
 long endTime = System.currentTimeMillis();
 double elapsedTime = (endTime - startTime)/1000.0;
 System.out.print("Fibonacci(" + myLong + ") = " + fibN);
 System.out.println(" took " + elapsedTime + " seconds"); 
 }
 }
 System.out.println("Goodbye!"); 
 }

 public static long fibonacci(long n) { 
 if (n <= 2)
 //enter the code for the base case here 
 else
 //enter the code for the recursive case here 
 } 
} 
 
 Test your program using the following values and record your results: 
 fibonacci(10) = _________ and took _________ seconds 
fibonacci(20) = _________ and took _________ seconds 
fibonacci(30) = _________ and took _________ seconds 
fibonacci(40) = _________ and took _________ seconds 
fibonacci(50) = _________ and took _________ seconds
 
 What do you notice about the time it takes to find the solution? 
 Part B – Computing a n 
 Write a program that uses a recursive algorithm to compute the value of a n where a is any number and n is an integer ≥ 0. Prompt the user for values of a and n and display the result. Recall that a n is the same as a a a*a...*a (n times) 
 
 As you develop your algorithm, what is the base case? 
 
 What is the recursive case? 
 Part C – Reverse a String 
 Write a program that uses a recursive algorithm to print a string in reverse. For example, if the user entered "abcdefg" then the program would display "gfedcba". Some String class methods that might be useful are length , substring , and charAt . Prompt the user for a string and display the result. 
 
 What is the base case? 
 What is the recursive case?