CODEWITHSUNDEEP
javarecursion
mythic
mythic

Reputation: 925

Finding the minimum in a given array using recursion

I don't quite understand the following recursive function. Here's the whole code:

public class Minimum {


  static int minimum(int [] array, int z, int k) {
    if (z == k)
      return array[z];

    int s = (z + k) / 2;

    int min1 = minimum(array, z, s);
    int min2 = minimum(array, s+1, k);

    return Math.min(min1, min2);
  }

  public static void main(String[] args) {
    int [] array = {4,5,7};

    int min = minimum(array, 0, array.length-1);
    System.out.println(min);
  }
}

I'll try to explain my thoughts about how I think it works.

If there is only one element in the array, we return that element (0 == array.length -1, if there is only 1 element)

if (z == k)
  return array[z];

I understand that we find the mean with the following code, correct?

int s = (z + k) / 2;

By using the following line, I think we only check the first half of the numbers, (until the mean) in the array?

int min1 = minimum(array, z, s);

And is the following code used to check the other half of the array?

int min2 = minimum(tabela, s+1, k);

We now call the Math.min function to get the minimum number in the array

return Math.min(min1, min2);

Upvotes: 1

Views: 2417

Answers (1)

Boris the Spider
Boris the Spider

Reputation: 61148

Lets think about this without code to begin with, lets find the minimum of the array a = [2,4,7,1].

Well, using the divide and conquer technique we can say the finding the minimum of a is the same as finding the minimum of the two halves of the array:

min([2,4,7,1]) = min(min([2,4]), min([7,1]))

And we can do this again

min([2,4,7,1]) 
    = min(min([2,4]), min([7,1])) 
    = min(min(min([2]),min([4])), min(min([7]),min([1])))

Now we have the termination case to the division, the min of a single element is that element, break this back out again:

min(min(min([2]),min([4])), min(min([7]),min([1])))
    = min(min(2,4), min(7,1))
    = min(2, 1)
    = 1

Magic.

So, how does the code you have shown work?

static int minimum(int [] array, int z, int k) {
    //if the we are examining the sub array consisting of one element
    if (z == k) {
        //the minimum of the array is that element
        return array[z];
    }
    //find the mid point of the array - also the mean of the two numbers, but that's not really relevant
    int s = (z + k) / 2;
    //find the minimum of the first half, by calling this function
    int min1 = minimum(array, z, s);
    //find the minimum of the second half, by calling this function
    int min2 = minimum(array, s+1, k);
    //return the smaller of the two halves
    return Math.min(min1, min2);
}

So, walking through the code with the above example:

minimum([2,4,7,1], 0, 3)

obviously z != k, so we split the array:

s = (0 + 3)/2 = 1 //due to integer division

so we call:

int min1 = minimum([2,4,7,1], 0, 1);
int min2 = minimum([2,4,7,1], 2, 3);

Which in turn splits this again, this time to the termination cases.

Upvotes: 6

Related Questions