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

## Answer

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