Skip to main content

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 an

Write a program that uses a recursive algorithm to compute the value of an 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 an is the same as aaa*a...*a (n times)

  1. 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.

  1. What is the base case?
  2. What is the recursive case?
No Comments
Back to top