In this lab you will design and implement recursive algorithms. The primary focus in this lab will be algorithms that make a single recursive call. Tail recursion will be explored. An improved recursive algorithm for computing Fibonacci numbers will be developed.

The first goal of this lab is to implement a couple of simple recursive methods that do not compute or return anything. Their sole purpose is to print integer values and give you some practice with recursion.

Sources files are provided below:

Count.java

public class Count {

public static void main(String args[]) { int n = getInt("Please enter an integer value greater than or equal to 0"); System.out.println("Should count down to 1"); countDown(n); System.out.println(); System.out.println("Should count up from 1"); countUp(n); } /** * countUp - A recursive function that counts up from 1 to n. * * @param n The integer value to count up to, */ private static void countUp(int n) { // IMPLEMENT THIS RECURSIVE METHOD } /** * countDown - A recursive function that counts down from n to 1. * * @param n The integer value to count down from. */ private static void countDown(int n) { // IMPLEMENT THIS RECURSIVE METHOD

} /** * Get an integer value * * @return An integer. */ private static int getInt(String rangePrompt) { Scanner input; int result = 10; //default value is 10 try { input = new Scanner(System.in); System.out.println(rangePrompt); result = input.nextInt(); } catch(NumberFormatException e) { System.out.println("Could not convert input to an integer"); System.out.println(e.getMessage()); System.out.println("Will use 10 as the default value"); } catch(Exception e) { System.out.println("There was an error with System.in"); System.out.println(e.getMessage()); System.out.println("Will use 10 as the default value"); } return result; } }

RecursiveFactorial.java

public class RecursiveFactorial {

/** * The basic recursive factorial. * * @param n The number to compute factorial of. * @return n factorial. */ public long basic(long n) { long result = 1; if (n > 1) result = n*basic(n-1); return result; } /** * The tail recursive version of factorial. * * @param n The number to compute factorial of. * @return n factorial. */ public long tailRecursive(long n) { // IMPLEMENT THIS METHOD USING THE RECURSIVE HELPER FUNCTION // AND RETURN SOMETHING APPROPRIATE return 0; }

/** * The tail recursive helper function for factorial. * * @param n The number to compute factorial of. * @param partial The partial result that is being built up. * @return n factorial. */

private long helper(long n, long partial) { long result = 0; // IMPLEMENT THIS TAIL RECURSIVE METHOD return result; }

}

RecursiveFibonacci.java

public class RecursiveFibonacci {

/** * basic - The simple version of fibonacci. * * @param n A positive integer. * @return The nth fibonacci number. */ public long basic(long n) { long result = 1; if( n <= 0) result = 0; else if (n == 1) result = 1; else result = basic(n-1) + basic(n-2); return result; } /** * better - A better version of fibonacci. (Height Limited Double Recursion) * * @param n A positive integer. * @return The nth fibonacci number. */ public long better(long n) { long result = 0; // IMPLEMENT THIS RECURSIVE METHOD return result; }

/** * tailRecursive - A tail recursive version of fibonacci. * (Height limited, Two problems per level) * * @param n A positive integer. * @return Tge nth fibonacci number. */ public long tailRecursive(long n) { // IMPLEMENT THIS METHOD USING A RECURSIVE HELPER FUNCTION // AND RETURN AN APPROPRIATE VALUE return 0; }

/** * secondMSB - Determine the value of the second most significant bit. * * @param n A positive integer * @return True if the second most significant bit is 1, false otherwise. */ public boolean secondMSB(long n) { // IMPLEMENT THIS METHOD AND RETURN AN APPROPRIATE VALUE return false; }

/** * reduceBy2ndMSB - Reduce the number by removing the second most significant bit * from the representation. * * @param n A positive integer > 1 * @return The integer value equivalent to removing the 2nd most significant bit * from n. */ public long reduceBy2ndMSB(long n) { long result = 1; // IMPLEMENT THIS METHOD return result; } }

RecursiveStringReplace.java

public class RecursiveStringReplace {

/** * replace - Replace all instances of one character by another. * * @param s The string to do the replacement on. * @param from The character to be replaced. * @param to the character to change to. * @return A new string with the appropriate characters replaced. */ public String replace(String s, char from, char to) { String result = null;

// IMPLEMENT THIS RECURSIVE METHOD

return result; } }

TimeFibonacci.java

public class TimeFibonacci { public static void main(String args[]) { System.out.println("What is the value of n?"); int n = getInt("Please enter an integer value greater than or equal to 0"); timeBasic(n);

/* System.out.println("How many times should the computation be performed?"); int trials = getInt("Please enter an integer value greater than or equal to 0"); timeBetter(n, trials); timeTailRecursive(n, trials); */ } public static void timeBasic(int n) { RecursiveFibonacci fibonacci = new RecursiveFibonacci(); long result; System.out.println("TIMING BASIC RECURSIVE FIBONACCI"); Calendar start = Calendar.getInstance(); result = fibonacci.basic(n); Calendar end = Calendar.getInstance(); long diff = end.getTime().getTime() - start.getTime().getTime(); System.out.println("Time to compute fibonacci(" + n + ") using basic recursion was " + diff + " milliseconds."); }

public static void timeBetter(int n, int trials) { RecursiveFibonacci fibonacci = new RecursiveFibonacci(); long result; System.out.println("TIMING BETTER RECURSIVE FIBONACCI"); Calendar start = Calendar.getInstance(); for(int i = 0; i< trials; i++) result = fibonacci.better(n); Calendar end = Calendar.getInstance(); long diff = end.getTime().getTime() - start.getTime().getTime();

System.out.println("Total time in milliseconds was: " + diff);

System.out.println("Time to compute a single call of fibonacci(" + n + ") using better recursion was " + ((double)diff)/trials + " milliseconds."); }

public static void timeTailRecursive(int n, int trials) { RecursiveFibonacci fibonacci = new RecursiveFibonacci(); long result; System.out.println("TIMING TAIL RECURSIVE FIBONACCI"); Calendar start = Calendar.getInstance(); for(int i = 0; i< trials; i++) result = fibonacci.tailRecursive(n); Calendar end = Calendar.getInstance(); long diff = end.getTime().getTime() - start.getTime().getTime();

System.out.println("Total time in milliseconds was: " + diff);

System.out.println("Time to compute a single call of fibonacci(" + n + ") using tail recursion was " + ((double)diff)/trials + " milliseconds."); }

/** * Get an integer value * * @return An integer. */ private static int getInt(String rangePrompt) { Scanner input; int result = 10; //default value is 10 try { input = new Scanner(System.in); System.out.println(rangePrompt); result = input.nextInt(); } catch(NumberFormatException e) { System.out.println("Could not convert input to an integer"); System.out.println(e.getMessage()); System.out.println("Will use 10 as the default value"); } catch(Exception e) { System.out.println("There was an error with System.in"); System.out.println(e.getMessage()); System.out.println("Will use 10 as the default value"); } return result; } }