George Francis George Francis - 3 months ago 10
Java Question

Understanding a program that finds the minimum value of an array with recursion

I need some help to understand the following program that finds the smallest number inside an array, I understand that in recursion you're supposed to divide the problem in a base case which ends the recursion, and into smaller steps that eventually grow down into the initial base case.

I understand that the base case is satisfied whenever the index reaches the final position in the array. How ever, I don't really understand how in the following program, the method would call itself back to continue advancing throughout the array.

Why does it continue checking the values of the full array instead of just stopping after checking the first value?

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;
}

Answer
if (elements[index] < val)
    return elements[index];

You're asking why it doesn't return there the first time, right? Well, it does, but that's fine, because it's already made the recursive call - it does that in this line:

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

So it will reach that call, descend a level, and repeat over and over until it reaches the base case termination condition:

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

Then as it goes back up the call stack, it will make the actual comparisons and find the least.

Make sense?