CS401 Lab 4: Methods, Arrays, Recursion

Introduction

We discussed arrays and the idea of recursion and looked at some simple examples in lecture. Before doing this lab, review the recent course notes and handouts (ex10.java) regarding recursion. In this lab you will consider and develop recursive methods to operate on an array of doubles.

Recall the three requirements of recursive algorithms:

1. There must be some recursive case, in which the algorithm "calls itself"
2. There must be some base case, in which no recursive call is made
3. The recursive calls must lead eventually to the base case

For example, recall the recursive code for the factorial problem (with error case removed):

public static int fact(int N)
{
	if(N <= 1) // Base case (N = 1 or N = 0)
		return 1;
	else
		return (N * fact(N-1));
			// Recursive case (N > 1)
}

Requirements 1. and 2. are clear from the code.  However, Requirement 3. is not quite as obvious, nor is it usually.  With some thought, we can convince ourselves that since each recursive call reduces the value of N by 1, the base case will eventually be reached regardless of the initial value of N.  As discussed in the course notes and textbook, the factorial problem also has a simple iterative solution, as shown below:

public static int fact_iter(int N)
{
	if (N <= 1)
		return 1; 
	else
	{
		int ans = 1;
		for (int i = N; i >= 2; i--)
			ans *= i;
		return ans;
	}
}

Note that each recursive call in the recursive version corresponds to an iteration in the iterative version.

Program

Implement the 4 methods below using a recursive algorithm for each:

public static double max(double [] data, int start)	// return the maximum value in the
							// array
public static double min(double [] data, int start)	// return the minimum value in the
							// array
public static double sum(double [] data, int start)	// sum the items in the array
							// and return the result
public static double ave(double [] data)		// call sum to get the sum
							// and then return the average

Keep in mind the 3 requirements for recursive algorithms and use the solutions to the factorial problem above and the power function (see handouts from lecture) for help.

Once you've completed the methods above, write a simple main program that does the following:

1. Asks the user how many items will be entered
2. Creates an array of type double of the correct size
3. Prompts the user and reads in each value
4. Calculates and prints out the max, min, sum and average using the methods above

Notes and Hints

You first need to determine what the base case (or cases) conditions will be. Then determine what the result (i.e. return value) will be in those cases. Next, determine how the problem recurses -- i.e. how the solution to the current problem can be calculated from the result of the recursive call. For example, in the factorial problem, the current problem relates to the recursive case in the following way:

CurrentProblemResult = (ParamValueFromThisProblem) * (RecursiveCall(ParamValueFromThisProblem - 1))

Think about the relationship of these cases in the recursive methods that you are implementing. Note that they are not all the same for the four methods.

As mentioned in lecture, if the base case is never reached, we have the error of Infinite Recursion, which is analogous to an infinite loop in iterative programs. However, practically speaking infinite recursion is not actually infinite. This is because each recursive call uses some of the computer's memory, so, eventually the program will run out of memory and crash with a run-time error (the interpreter prevents the program from actually using all of the computer's memory). To see this, comment out the base case for the fact method so that it always makes the recursive call. You will see the following error:

Exception in thread "main" java.lang.StackOverflowError

This indicates that the run-time stack (part of the memory allocated for your program) has gone past its allowed size.  If you get this error in your program, carefully trace it by hand to see if your recursive calls are in fact leading to your base case (Requirement 3. above).

Thanks to Dr. Ramirez for a large portion of this lab