Java recursive functions

Question

I don't quite understand recursion yet and I have some homework that I can't solve. Does anyone have an idea?

Task 1: Implement an int-method max(int[]arr, int i) which returns the maximum of all elements of arr with an index <= i.

This is my code thus far:

private static int max = 0;

private static int max(int[] arr, int i) {
    if (i >= 0 && i < arr.length) {
        if (arr[i] >= max) {
            max = arr[i];
        }

        max(arr, i - 1);
    }
    return max;
}

Actually it works, but it's bad style, so my question is: How can I implement the recursive method without the private static int max? I am not allowed to add a third parameter to the method.

Task 2: Implement a boolean-method containsValue(int[] arr, int val) which returns true if one of the elements of arr matches val. The method should have two recursive calls: one which searches the first half of the array and one that searches the second half. You can use Arrays.copyOfRange(...).

This is my code:

private static boolean containsValue(int[] arr, int val) {
    if (arr.length > 1) {
        if (arr[arr.length - 1] == val) {
            return true;
        }
        return containsValue(Arrays.copyOfRange(arr, 0, arr.length-1), val);
    }

    return false;
}

This also works and I understand why, but obviously the method doesn't have two recursive calls. Every attempt to implement the method dividing the array in two halves was a huge failure. Can anyone help me?

Answer 1

For recursion in general, you need the structure:

if the problem is simple enough to answer easily:
   return the answer
else:
   split the problem into two parts
   recurse to get the answer
   return the answer

For max() this is:

if the input list is of size 1:
   return the only element of the list
else
   split the list into a head (first element) and a tail (rest of the list)
   recurse to get the max of tail
   return the head or the max of tail, whichever is largest

Or in Java:

int max(int[] list) {
   if(list.length == 1) {
        return list[0];
   } else {
        return Math.max(list[0], max(tail(list)));
   }
}

(You'll need to implement int[] tail(int[] list) yourself, using Arrays.copyOfRange())

This implementation does not handle a zero-length input list -- it would be a nonsensical invocation, with undefined results. If you wanted to, you could make it throw a more informative exception.

---

Your second assignment could be written in essentially the same way, except that now there are two 'easy' cases in which we don't recurse:

• If the input list is empty, the answer is false
• If the first element of the input list is what we're looking for, the answer is true
• Otherwise it's not 'easy', so recurse.

So:

boolean contains(int value, int[] list) {
   if(list.length == 0) {
        return false;
   } 

   if(list[0] == value) {
      return true;
   }

   return contains(value, tail(list));
}

... except that you've been told to recurse into the first half, then the second half of the array. So, just do as you've been told:

int contains(int value, int[] list) {
   if(list.length == 0) {
      return false;
   }

   if(list.length == 1) {
       return list[0] == value;
   }

   return contains(value, firstHalf(list)) || 
          contains(value, secondHalf(list));
}

You will need to write your own firstHalf() and secondHalf() implementations, again using Arrays.copyOfRange(). Ensure that when the input list is an odd length, that the middle value is in only one of the halves.

---

Notice how declarative this is - it almost translates directly into an English statement: "I know it's not there if the list is empty. It's there if it's the first element of the list, or if the tail of the list contains it."

---

Do note that in neither of these cases is recursion an efficient way to achieve this functionality in Java. But I'm sure your teacher is guiding you towards more practical and necessary applications of recursion.