[FIXED] I need help understanding how this algorithm that finds smallest value of an array using recursion works

Issue

I'm currently taking data structures and am learning about recursions. The code/algorithm posted below is supposed to find the smallest value of an array using recursion. However, I'm having trouble understanding how it works. My teacher's explanation wasn't very helpful so if anyone knows how to explain this well I would really appreciate it!

public class Recursive {

    public static int minimum(int array[], int first, int last) {
        int answer;
        int mid;
        int minFirst;
        int minSecond;
        
        if(first == last)
            return array[first];
        else {
            mid = (first + last) / 2;
            minFirst = minimum(array, first, mid);
            minSecond = minimum(array, mid + 1, last);
        }
        if(minFirst < minSecond)
            answer = minFirst;
        else
            answer = minSecond;
        return answer;
    }

}

Solution

The method finds the minimum element in an array in the range specified by first and last. So minimum(arr, 4, 6) would find the minimum among arr[4], arr[5] and arr[6].

Let's see how it does this.

If first is the same as last, there is only one element in the specified range, and that is array[first] (or array[last], which is the same thing). The smallest element must be that element, so return array[first].

Otherwise, we want to split the range into two halves. To do this, we first find the mid point of the range by doing (first + last) / 2 - calculating the average of first and last. Then the two halves are:

• from first to mid
• from mid + 1 to last

Then we find the minimum element in each of those halves, hence:

• minimum(array, first, mid)
• minimum(array, mid + 1, last)

I understand that it's counterintuitive how we can use the minimum method when we haven't even finished declaring what it does, but let's trust ourselves that minimum will do what it's supposed to do - find the minimum between the ranged specified by the last two arguments.

Then we compare these minimums. Whichever of these minimums is smaller, is the minimum element in the whole range (what the last if statement is doing).

Answered By - Sweeper
Answer Checked By - Senaida (JavaFixing Volunteer)