How do I find the minimum value in an array using recursion and only one parameter?

Question

My teacher challenged us to find the minimum value in an array using recursion, but you can only have one parameter which is the array.

public int minimum(int arry[])

Answer 1

The trick with these is to try to define the problem in a recursive manner, that is, in a way that uses the operation itself in its definition along with a "base case" that does not. For example, in this case, think about what the "minimum value in an array" is:

• For an array of size 1, the minimum value is just that one element.
• For a larger array, the minimum value is the smaller of the first element and the minimum value in the remainder of the array.

So you have your base case (array of size 1), and your recursion. That should be enough for you to go on.

Answer 2

Try below code:

Concept: Eliminate larger value from array and return min when you have only one element in array.

public int min(int[] n) {
        if (n.length > 1) {
            int a = n[0];
            int b = n[1];
            int[] newN = new int[n.length - 1];

            for (int i = 0; i < newN.length; i++) {
                if (i == 0)
                    newN[i] = a < b ? a : b;
                else
                    newN[i] = n[i + 1];
            }
            return min(newN);

        }
        return n[0];
    }

Answer 3

You have to pass successively smaller arrays to the next iteration:

public int minimum(int arr[]) {
    if (arr == null || arr.length == 0)
        throw new IllegalArgumentException();
    if (arr.length == 1)
        return arr[0];
    int min = minimum(Arrays.copyOfRange(arr, 1, arr.length));
    return arr[0] < min ? arr[0] : min;
}

But this is strictly an academic exercise - "do not try this at home".

Answer 4

    public static int[] removeElement(int element,int[] original){
        int[] n = new int[original.length - 1];
        System.arraycopy(original, 0, n, 0, element );
        System.arraycopy(original, element+1, n, element, original.length - element-1);
        return n;// http://stackoverflow.com/questions/4870188/delete-item-from-array-and-shrink-array
    }
    public static int [] shift(int[] original){
        int[] a = new int[original.length];
        for(int k = 1 ; k < original.length;k++){
            a[k-1] = original[k];
        }
        a[original.length-1] = original[0];
        return(a);
    }
    public static int minimum(int[] arr){ //Process of elimination
        if(arr.length==1){ //Base Case
           return(arr[0]); 
        }
        if(arr[0]>=arr[1]){// reduction step
           return(minimum(removeElement(0,arr)));
        }else{ // tread water
            return(minimum(shift(arr)));
        }
    }// There is always a better way but this sould satisfy your teacher.

Give Pratik Popat an up-vote for copying my mediocre logic.

Answer 5

public static int min(int[] n) {
    if(n.length == 1)//base case
        return(n[0]);
    int a = n.length%2 == 0 ? 0:1;      //Awesome sauce syntax http://www.cafeaulait.org/course/week2/43.html
    int[] r =new int[n.length/2 + a];   // reduce by a factor of 2 each iteration
    for(int k = 0 ; k < n.length/2 + a ; k++){    //While copying to a smaller array you might as well make comparisons.
        r[k] = n[k]<=n[n.length-k-1] ? n[k] : n[n.length-k-1];//compare the beginning and end of your array, take the smaller of the two.
    }   //In the case that you have an odd number of elements the middle is always copied trough to the next iteration
    return(min(r));//This is where the recursion happens.
}   // There is always a better way but this should satisfy your teacher.