Package algs11

Class MyRecursion

java.lang.Object

algs11.MyRecursion

public class MyRecursion
extends Object

This is a skeleton file for your homework. Edit the sections marked TODO. You may add new functions. You may also edit the function "main" to test your code. You must not add static variables. You MAY add static functions, just not static variables. It is okay to add functions, such as

     public static double sumHelper (double[] list, int i, double sumSoFar) {
 

but it is NOT okay to add static variables, such as

 public static int x;
 

As for homework 1, you must not change the declaration of any method. You can edit the main function all you want. I will not run your main function when grading.

Constructor Summary

Constructors

Constructor	Description
MyRecursion()

Method Summary

Modifier and Type	Method	Description
private static double[]	doublesFromString(String s)
static void	draw(double centerX, double centerY, double radius)	PROBLEM 3: The following function draws mickey mouse, if you call it like this from main:
static long	fibonacci(int n)
static void	main(String[] args)	A test program, using private helper functions.
static void	main1(String[] args)
static double	minValue(double[] list)	recursive version
private static double	minValueHelper(double[] list, int i, double result)
static double	minValueI(double[] list)	iterative version
static void	reverse(double[] a)
static void	reverseI(double[] a)	PROBLEM 2: Do the same translation for this in-place reverse function You should write a helper method.
static void	runFibonacciLoop()	PROBLEM 5: The implementation of terribleFibonacci is TERRIBLE! Write a more efficient version of fibonacci.
static void	runTerribleLoop()	PROBLEM 4: Run runTerribleLoop for one hour.
static double	sum(double[] a)
static double	sumI(double[] a)	PROBLEM 1: Translate the following sum function from iterative to recursive.
static long	terribleFibonacci(int n)
private static void	testFibonacci(long expected, int n)
private static void	testMinValue(String list)
private static void	testReverse(String list)
private static void	testSum(String list)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

MyRecursion

public MyRecursion()

Method Details

minValueI

public static double minValueI(double[] list)

iterative version

minValue

public static double minValue(double[] list)

recursive version

minValueHelper

private static double minValueHelper(double[] list,
 int i,
 double result)

sumI

public static double sumI(double[] a)

PROBLEM 1: Translate the following sum function from iterative to recursive. You should write a helper method. You may not use any "fields" to solve this problem (a field is a variable that is declared "outside" of the function declaration --- either before or after).

sum

public static double sum(double[] a)

reverseI

public static void reverseI(double[] a)

PROBLEM 2: Do the same translation for this in-place reverse function You should write a helper method. You may not use any "fields" to solve this problem (a field is a variable that is declared "outside" of the function declaration --- either before or after).

reverse

public static void reverse(double[] a)

draw

public static void draw(double centerX,
 double centerY,
 double radius)

PROBLEM 3: The following function draws mickey mouse, if you call it like this from main:

 draw (.5, .5, .25);
 

Change the code to draw mickey moose instead. Your solution should be recursive. Before picture: http://reed.cs.depaul.edu/efredericks/ds1/images/MickeyMouse.png After picture: http://reed.cs.depaul.edu/efredericks/ds1/images/MickeyMoose.png You may not use any "fields" to solve this problem (a field is a variable that is declared "outside" of the function declaration --- either before or after).

runTerribleLoop

public static void runTerribleLoop()

PROBLEM 4: Run runTerribleLoop for one hour. You can stop the program using the red "stop" square in eclipse. Fill in the OUTPUT line below with the numbers you saw LAST --- edit the line, replacing the two ... with what you saw: OUTPUT: terribleFibonacci(...)=... // TODO Comment: the code uses "long" variables, which are like "int", but bigger. It's because fibonacci numbers get really big really fast.

terribleFibonacci

public static long terribleFibonacci(int n)

runFibonacciLoop

public static void runFibonacciLoop()

PROBLEM 5: The implementation of terribleFibonacci is TERRIBLE! Write a more efficient version of fibonacci. Do not change runFibonacciLoop or runFibonacciSomeValues. To make fibonacci run faster, you want it so that each call to fibonacci(n) computes the fibonacci numbers between 0 and n once, not over and over again. Comment: You will want to use a local variable of type "long" rather than type "int", for the reasons discussed above. Comment: At some point, your fibonacci numbers might become negative. This is normal and expected. http://en.wikipedia.org/wiki/Integer_overflow We discuss this at length in our systems classes. You may not use any "fields" to solve this problem (a field is a variable that is declared "outside" of the function declaration --- either before or after). You may use a loop on this problem. You do not need to use recursion.

fibonacci

public static long fibonacci(int n)

main

public static void main(String[] args)

A test program, using private helper functions. See below. To make typing tests a little easier, I've written a function to convert strings to arrays. See below. You can modify this -- it is not graded.

main1

public static void main1(String[] args)

testSum

private static void testSum(String list)

testMinValue

private static void testMinValue(String list)

testReverse

private static void testReverse(String list)

testFibonacci

private static void testFibonacci(long expected,
 int n)

doublesFromString

private static double[] doublesFromString(String s)