Finding the minimum of an array using recursion?

Question

Ok, so I've been trying to wrap my head around recursion in Java and I can accomplish easy tasks such as sum, reversing etc. but I have been struggling to do this exercise:

I'm trying to find the minimum number in an array using recursion but keep getting an answer of 0.0.

My understanding for recursion is that there I need to increment one element and then provide a base case that will end the recursion. I think I'm messing up when I have to return a value and when is best to call the recursion method.

This is what I have so far:

public static double findMin(double[] numbers, int startIndex, int endIndex) {

double min;
int currentIndex = startIndex++;

if (startIndex == endIndex)
    return numbers[startIndex];

else {
    min = numbers[startIndex];
    if (min > numbers[currentIndex]) {
        min = numbers[currentIndex];
        findMin(numbers, currentIndex, endIndex);
    }
            return min;
}       
} //findMin

Override

Answer 1

There are a variety of problems in this code including:

• You don't use the result of the recursive findMin call.
• startIndex will be the same for every call to findMin, because currentIndex is being set to the value of startIndex before startIndex is incremented.
• If the number at index 1 in the array is <= the number at index 0, you just return that number without even making the recursive call.

Levigate

So, should the return statement occur before I call the recursive findMin method? Also, I'm not understanding how the startIndex is not changing. When I call the recursive findMin method, I'm using the parameters with currentIndex (instead of startIndex), which should then be passed as a new startIndex, correct? I think I'm starting to confuse myself :( – Override

@user699302: The problem is the currentIndex = startIndex++. When startIndex is 0, currentIndex becomes 0 and startIndex becomes 1. When you call findMin, you pass it currentIndex, so in that call startIndex will once again be 0, leading to infinite recursion and a stack overflow. – Levigate

Answer 2

Here's a simplified version:

public static double min(double[] elements, int index) {

  if (index == elements.length - 1) {
    return elements[index];
  }

  double val = min(elements, index + 1);

  if (elements[index] < val)
    return elements[index];
  else
    return val;
}

Hanforrd

Answer 3

Hint: You're calling findMin recursively, but then not using its return value.

What's the relationship between (1) the min of the whole array, (2) the first element, and (3) the min of everything apart from the first element?

Ligetti

So, I should call the findMin method recursively and assign the return value to...? This is where I'm confused. Do I define the return value before calling the findMin method? – Override

Answer 4

A few observations in addition to the first answer:

• int currentIndex = startIndex++; - you're going to miss your first element here. In general, you don't want to modify the input to your recursive function. Work off the input and generate new values when you're ready to call the function again - i.e. 'findMin(numbers, currentIndex+1, endIndex)'

Emiliaemiliaromagna

The default value of a double doesn't come in to play here, since min is always assigned to a value from the array before it's read. Really, it shouldn't be declared until the point where it's assigned though. – Levigate