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?

@nafas No, these are specific questions about recursion. Recursion may not be the best way to solve this problem, while OP specifically needs it for homework. A general review is not what's asked for here, but it clearly shows research, effort and a small amount of understanding. OP simply wants a specific, different method of implementation. I dare say it's already an MCVE, so why wouldn't it be fit for Stack Overflow? — Mast
– Mast, Commented Jan 2, 2018 at 16:43
For the 1st one, consider comparing the current value with the value returned from a recursive call. This way you can eliminate the static var. — 001
– 001, Commented Jan 2, 2018 at 16:44
@Mast ** in my opinion **(and yes we cast vote based on our opinion), Homeworks are there to make students fail, only failure can bring about the best of us. a code review will show what you did wrong, whereas a new solution will only provide a better answer to a homework. in such case, one will receive the full mark and never bother to find out why!!!! — nafas
– nafas, Commented Jan 2, 2018 at 16:54

slim · Accepted Answer · 2018-01-02 17:28:22Z

4

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.

edited Jan 2, 2018 at 17:28

answered Jan 2, 2018 at 16:54

slim

41.5k14 gold badges101 silver badges131 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

001 Over a year ago

The teacher has given the signature of the first method as int max(int[]arr, int i) where i is the max index to check. So you can simplify the method to something like: ideone.com/IN5aPR

slim Over a year ago

I can, but so can you -- in that case you don't need to use copyOfRange() -- you can pass the same array every time. if(list.length == 1) becomes if(i = list.length -1) (i.e. "we're on the last item") and instead of examining list[0] every time, you examine list[i]. And recurse using i + 1.

Collectives™ on Stack Overflow

Java recursive functions

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related