-5

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[])

6
  • Well. You basically have 2 options. 1. Use a static field to keep count of which elements are being compared as you pass the array recursively. 2. Create a subArray by chopping of the first element in each recursive call. Mar 9, 2015 at 5:56
  • @TheLostMind I am strongly against option 1, or even the idea of suggesting it as an option. It is not in the spirit of the assignment and certainly doesn't teach the OP how to frame problems recursively (which is the point). Also, it is essentially the same as a second function parameter, with the exception that it is not re-entrant or thread-safe.
    – Jason C
    Mar 9, 2015 at 6:14
  • @JasonC - I think the question itself is flawed. Ideally, when using recursion, you must also pass a count field. Otherwise like Bohemian's answer does, you have to copy the entire array. Mar 9, 2015 at 6:22
  • @TheLostMind Passing the current index to avoid copying the array is merely a performance optimization for a Java implementation. It does not indicate a flaw in the question and is incidental to the problem at hand.
    – Jason C
    Mar 9, 2015 at 6:24
  • @JasonC - If you want the answer to sue recursion properly, then frame the question properly. I say allow only int to be passed in the question, and then keep the array global. This will still be recursion. Why confuse the OP? . I am merely pointing out a flaw in the teacher's question. :P Mar 9, 2015 at 6:27

5 Answers 5

2

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.

1
  • Good answer, better than mine. +1
    – Shashank
    Mar 9, 2015 at 6:21
1

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];
    }
1
  • This answer would be more useful if you could explain why you chose to do it this way, what benefits it may have over a more traditional approach, and what process led you to arrive at this method. Otherwise it does not help the OP learn any real skills.
    – Jason C
    Mar 9, 2015 at 7:18
0

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

3
  • 1
    Not a big fan of answers that the OP can copy and paste into his assignment without being forced to think about it first; especially to posts that only questionably belong here.
    – Jason C
    Mar 9, 2015 at 6:18
  • Will it explode if you try this at home?
    – rene
    Mar 9, 2015 at 7:26
  • @rene It's hard to think of a less efficient algorithm
    – Bohemian
    Mar 9, 2015 at 9:50
-1
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.
3
  • 1
    Ignoring all the other issues with posting code-only answers, your "awesome sauce syntax" (which I'm assuming is your name for the elementary ?: operator) n.length % 2 == 0 ? 0 : 1 is exactly the same as just n.length % 2 alone.
    – Jason C
    Mar 9, 2015 at 7:47
  • I needed a line of code to post the link on. Also I used a a few times so why not?
    – kpie
    Mar 9, 2015 at 7:51
  • Er... what? I think you misunderstood: You don't need the ? 0 : 1 on that line. n.length % 2 is already 0 or 1. See cafeaulait.org/course/week2/15.html for more info on the % operator.
    – Jason C
    Mar 9, 2015 at 7:54
-1
    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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.