Java Homework: Recursion

In the interest of improving faster, I’ll be posting my intro to comp sci assignments for feedback and constructive criticism. This week’s lab was recursion.

  1. double product(double[] a, int start, int end) that calculates the product of array elements from the index start to index end.
  2. boolean allEqual(int[] a, int start, int end) that checks if all elements in the array a from start to end are equal.
  3. void arraycopy(double[] src, int start, double[] tgt, int start2, int len) that copies len elements from the location start of array src to the location start2 of array tgt. (That is, it works the same as System.arraycopy.) Hint: when len is zero, do nothing, otherwise copy one element and then recursively copy len-1 elements.
  4. boolean linearSearch(int[] a, int x, int start, int end) that checks if the array a contains the element x anywhere between the indices start and end.
public class recursion {

    public static double product(double[] a, int start, int end) {
        if (start == end) {
            return a[start];
        }
        else {
            return a[start] * product(a, start+1, end);
        }
    }

    public static boolean allEqual(int[] a, int start, int end) {
        if (start == end) {
                return true;
        }
        else {
            if (a[start] == a[start+1]) {
                return allEqual(a, start+1, end);
            }
            else {
                return false;
            }
        }
    }

    public static void arraycopy(double[] src, int start, double[] tgt,
    int start2, int len) {
        if (len > 0 && start < src.length && start2 <
        tgt.length) {
            tgt[start2] = src[start];
            arraycopy(src, start+1, tgt, start2+1, len-1);
        }
    }

    public static boolean linearSearch(int[] a, int x, int start, int end) {
        if (start == end) {
            return false;
        }
        else {
            if (a[start] == x) {
                return true;
            }
            else {
                return linearSearch(a, x, start+1, end);
            }
        }
    }

        public static void main(String[] args) {
        int[] intsNotEqual = new int[5];
        int[] intsEqual = new int[5];
        double[] doubles = new double[5];
        int[] newArray = new int[6];

        //Get Ready
        System.out.println("Unequal numbers:");
        for(int i = 0; i < intsNotEqual.length; i++) {
            intsNotEqual[i] = i*2;
            System.out.println(i*2);
        }

        System.out.println("Equal numbers:");
        for(int i = 0; i < intsEqual.length; i++) {
            intsEqual[i] = 4;
            System.out.println(i*2);
        }

        System.out.println("Doubles:");
        for(int i = 0; i < doubles.length; i++) {
            doubles[i] = i*2;
            System.out.println(i*2);
        }

        System.out.println("Product of array elements: " + product
        (doubles, 1, 4));

        System.out.println("Equivalency check on unequal numbers: "
        + allEqual(intsNotEqual, 0, 3));

        System.out.println("Equivalency check on equal numbers: " +
        allEqual(intsEqual, 0, 3));

        System.out.println("Search for number not in array: " +
        linearSearch(intsEqual, 7, 0, 4));

        System.out.println("Search for number in array: " +
        linearSearch(intsNotEqual, 4, 0, 4));
    }

}

Code formatting by Format My Source Code, which I found through Jolie O’Dell.

5 thoughts on “Java Homework: Recursion

  1. Those aren’t the best example problems for teaching recursion, but they’ll do. (Why recurse and add to the program stack when a simple For loop would be lighter on system resources?)

    Anyway, I’d give you a Pass for understanding recursion in your code. One thing to look at is bounds checking in your first two solutions and the fourth solution (it’s not recursion-related but array-related, and would be important in production code, as you’d get an error for referring to an element outside an array). Your third solution does appear to take care of any bounds issues.

    Finally, with your fourth solution, what if you were only wanting to search one particular element of the array? Sure, a simple if a[5] = 3 would do, but your code above doesn’t return True if calling linearSearch(a, 3, 5, 5) when a[5] does equal 3. Replacing the first If statement with a if (start >= end) would fix that.

  2. Awesome, thank you.

    I meant to go back and add the bounds checking to the first 2, but I got swept up in the joy of watching it compile with no errors and my crappy test cases telling me that things seemed a-okay.

    1. Dude, they’re still teaching intro classes with Java rather than Python. Test-driven development never came up once.

      I’m super lucky that I live with a great developer who enjoys talking about programming and has a knack for simple analogies and explanations.

Leave a Reply to Mike Cancel reply

%d bloggers like this: