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

To better understand how the code works, lets put some print statements. This will tell us what data each recursion of the method is working on.
I've put some comments in code.

public class Test {

    public static void main(String[] args) throws Exception {
        int[] arr = {4,3,2,1};
        System.out.println("\nThe smallest element is : " +minimum(arr, 0, 3, 1));
    }
    
    //this method finds smallest element within given range in an array
    public static int minimum(int array[], int first, int last, int indent) {
        //lets print what each recursion is working on
        int[] subArray = Arrays.copyOfRange(array, first, last+1);
        System.out.println(" ".repeat(indent) + "Invoked with: first=" 
                    + first + " last=" + last 
                    + " Array=" + Arrays.toString(subArray));
        int answer;
        int mid;
        int minFirst;
        int minSecond;
        
        if(first == last) {
            System.out.println(" ".repeat(indent) + "Selected " + array[first]);
            return array[first];
        }
        else {
            //divide the range in half
            mid = (first + last) / 2;
            //find smallest element from first half
            minFirst = minimum(array, first, mid , indent + 3);
            //find smallest element from second half
            minSecond = minimum(array, mid + 1, last, indent +3);
        }
        
        //select smallest element from both halves
        if(minFirst < minSecond)
            answer = minFirst;
        else
            answer = minSecond;
        System.out.println(" ".repeat(indent) + "Selected " + answer + " from " + minFirst + ", " + minSecond);
        return answer;
    }

}

Output:

 Invoked with: first=0 last=3 Array=[4, 3, 2, 1]
    Invoked with: first=0 last=1 Array=[4, 3]
       Invoked with: first=0 last=0 Array=[4]
       Selected 4
       Invoked with: first=1 last=1 Array=[3]
       Selected 3
    Selected 3 from 4, 3
    Invoked with: first=2 last=3 Array=[2, 1]
       Invoked with: first=2 last=2 Array=[2]
       Selected 2
       Invoked with: first=3 last=3 Array=[1]
       Selected 1
    Selected 1 from 2, 1
 Selected 1 from 3, 1

The smallest element is : 1

You can also use debug feature of your IDE like Eclipse.

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).

Just about every recursion algorithm consists of 2 crucial parts:

The trivial case(s)

All recursive algorithms give an instantaneous answer (and do not recurse) for trivial input.

In this specific case, the trivial input case is when 'first' and 'last' are equal to each other: The intent of the method is to return the smallest value found amongst all values starting at index 'first' and ending at index 'last'. When first and last are equal, there is only one number to look at. Trivially then, 'what is the smallest number amongst this giant collection of.... 1 number', is.. that number. That is the trivial case.

The progression towards the trivial case.

All other cases are resolved by first invoking your own method again, but with modified inputs - the inputs should be modified so that they have moved closer towards the edge case in some fashion. Sometimes, you invoke your own method multiple times, but all such invocations must all be guaranteed to be closer to the trivial case, and then you combine the separate answers.

In this case, the problem is stated as:

To find the smallest number from a list of numbers, first, lop the list of numbers into two roughly equal parts. These lists are smaller, and therefore, simpler, so we can just ask ourselves to calculate the answer for these smaller lists - that's okay, we moved them towards the trivial case, we can do that. Then, combine the two obtained answers: Just return the smallest answer, chunking out the larger one.

That's it.

That's all you need to write recursive code. It makes sense if you think about it in these terms: For any input, the algorithm is to restate the problem in terms of a simple operation applied to the result of calculating a slightly simpler question.

The result of that slightly simpler question is done the same way: By applying a simple operation to the result of calculating an even simpler question.

Rinse and repeat until the question is so incredibly simple, the answer is obvious and can be provided immediately.

Let's add more log, and you can see clearly:

import java.util.Arrays;
import java.util.concurrent.atomic.AtomicInteger;

public class Recursive {

    private static AtomicInteger step = new AtomicInteger();

    public static int minimum(int array[], int first, int last) {
        int answer;
        int mid;
        int minFirst;
        int minSecond;
        int currentStep = step.incrementAndGet();
        System.out.println("=================== step: " + currentStep + "=============");
        int[] currentArray = new int[last - first];
        System.arraycopy(array, first, currentArray, 0, currentArray.length);
        System.out.println("current array(" + first + ", " + last + "): " + Arrays.toString(currentArray));
        System.out.print(String.format("first(%d) == last(%d): %b", first, last, first == last));
        if(first == last) {
            System.out.println(", so min = " + array[first]);
            return array[first];
        }
        else {
            System.out.println(", so divide 2 the array");
            mid = (first + last) / 2;
            minFirst = minimum(array, first, mid);
            int minFirstStep = step.get();
            minSecond = minimum(array, mid + 1, last);
            int minSecondStep = step.get();
            System.out.print(String.format("compare min of step[%d] and step[%d]: %d < %d = %b",
                                           minFirstStep,
                                           minSecondStep,
                                           minFirst,
                                           minSecond,
                                           minFirst < minSecond));
        }
        if(minFirst < minSecond)
            answer = minFirst;
        else
            answer = minSecond;
        System.out.println(", so min = " + answer);
        return answer;
    }

    public static void main(String[] args) {
        int array[] = {1, 4, 7, 8, 5, 2};
        int min = minimum(array, 0, array.length - 1);
        System.out.println("min is: " + min);
    }

}

Output:

=================== step: 1=============
current array(0, 5): [1, 4, 7, 8, 5]
first(0) == last(5): false, so divide 2 the array
=================== step: 2=============
current array(0, 2): [1, 4]
first(0) == last(2): false, so divide 2 the array
=================== step: 3=============
current array(0, 1): [1]
first(0) == last(1): false, so divide 2 the array
=================== step: 4=============
current array(0, 0): []
first(0) == last(0): true, so min = 1
=================== step: 5=============
current array(1, 1): []
first(1) == last(1): true, so min = 4
compare min of step[4] and step[5]: 1 < 4 = true, so min = 1
=================== step: 6=============
current array(2, 2): []
first(2) == last(2): true, so min = 7
compare min of step[5] and step[6]: 1 < 7 = true, so min = 1
=================== step: 7=============
current array(3, 5): [8, 5]
first(3) == last(5): false, so divide 2 the array
=================== step: 8=============
current array(3, 4): [8]
first(3) == last(4): false, so divide 2 the array
=================== step: 9=============
current array(3, 3): []
first(3) == last(3): true, so min = 8
=================== step: 10=============
current array(4, 4): []
first(4) == last(4): true, so min = 5
compare min of step[9] and step[10]: 8 < 5 = false, so min = 5
=================== step: 11=============
current array(5, 5): []
first(5) == last(5): true, so min = 2
compare min of step[10] and step[11]: 5 < 2 = false, so min = 2
compare min of step[6] and step[11]: 1 < 2 = true, so min = 1
min is: 1