Comparing Recursive Running Times

In this file, you'll find two recursive methods (min1 and min2) for finding the minimum of an array. Your task is to finish the main method, which should time each method to determine which one is faster.

To do this:

Make some test arrays of various sizes.

Run and time each method on each test case.

Print out the data in a table.

There are quite a few different arrays that you could test, and quite a few sizes.

For sizes, use 1 <= size <= 33.

For content, try at least three ways of filling the array:

Fill with data in ascending order. (ex. [0, 1, 2, ..., size-1])

Fill with data in descending order. (ex. [size-1, size-2, ..., 1, 0])

Fill with random data.

Note: your program doesn't have to test all of these at once. You can comment in/out different array generation code, so that a different type of array is tested each run.

The code:

import java.util.Random;

public class RecursionTester { // suppose you are given the following two recursive // methods for finding the minimum of an array: // version 1: public static int min1(int[] array) { return min1(array, array.length); } public static int min1(int[] array, int n) { if(n <= 0) { // no minimum exists throw new IllegalArgumentException("array is empty"); } else if(n == 1) { // base case: if there's a single element, that's it! return array[0]; } else { // recursive case: it's either the last element, or the // minimum of the first n-1 elements if(min1(array, n-1) < array[n-1]) { return min1(array, n-1); } else { return array[n-1]; } } } // version 2: public static int min2(int[] array) { return min2(array, array.length); } public static int min2(int[] array, int n) { if(n <= 0) { // no minimum exists throw new IllegalArgumentException("array is empty"); } else if(n == 1) { // base case: if there's a single element, that's it! return array[0]; } else { // recursive case: it's either the last element, or the // minimum of the first n-1 elements int tmp = min2(array, n-1); if(tmp < array[n-1]) { return tmp; } else { return array[n-1]; } } } // main method public static void main(String[] args) { // TODO: determine which of the previous two methods is faster! // TODO: (1) create some test arrays (of various sizes) // TODO: (2) time how long it takes to find the minimum with each method // TODO: (3) display your results in a table, that can easily be graphed } }