CODEWITHSUNDEEP
javaalgorithmrecursion
user4685154
user4685154

Reputation:

Maximum minus minimum in an array

I am trying to find range(max - min) of an array using recursion. Since, there can be only one return value, I am kind of confused how to go about this problem. What I have done so far is to find maximum and minimum recursively and then use this in range function to find the range. I was wondering if it was possible to do everything in just range function somehow recursively.

public static int max(int[] array, int N) {
    int maximum;

    if (N >= array.length) {
        maximum = Integer.MIN_VALUE;
    } else {
        maximum = max(array, N + 1);
        if (array[N] > maximum) {
            maximum = array[N];
        }
    }

    return maximum;
}

public static int min(int[] array, int N) {
    int minimum;

    if (N >= array.length) {
        minimum = Integer.MAX_VALUE;
    } else {
        minimum = min(array, N + 1);
        if (array[N] < minimum) {
            minimum = array[N];
        }
    }

    return minimum;
}   

public static int range(int [] array)
{
    int max1 = max(array , 0);
    System.out.println(max1);
    int min1 = min(array , 0);
    System.out.println(min1);
    int range = max1 - min1;

    return range;
}

Upvotes: 1

Views: 2445

Answers (5)

Sampisa
Sampisa

Reputation: 1583

This problem doesn't have any improvement from recursion, since it is a iterative problem that - instead - can result in performance issue due to the growing of stack size, in particular for big arrays. Anyway, a more classical example in java 7 can be the following, where you can use a minimal "Couple" class to store min/max values

public class MaxMinRecurse {

    void evalMaxMinInInterval(Couple maxmin, int pos, int[] values) {
        if (pos >= values.length)
            return;
        int x = values[pos];
        if (x < maxmin.min) {
            maxmin.min = x;
        } else if (x > maxmin.max) {
            maxmin.max = x;
        }
        evalMaxMinInInterval(maxmin, pos + 1, values);
    }

    public static void main(String[] args) {
        MaxMinRecurse mmr = new MaxMinRecurse();
        int[] values = { 1, 5, 3, 4, 7, 3, 4, 13 };
        Couple result = mmr.new Couple();
        mmr.evalMaxMinInInterval(result, 0, values);
        System.out.println("Max: " + result.max + ", Min:" + result.min);
    }

    class Couple {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
    }

}

Upvotes: -2

walen
walen

Reputation: 7273

Your algorithm seems waaaay too complicated for what you're trying to do.

It's not clear if using recursion is a requirement. If it is not, what about this?

public int range (int[] array) {
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for (int elem : array) {
        if (elem < min) min = elem;
        if (elem > max) max = elem;
    }
    return (max - min);
}

On mobile so I cannot test any code, but it should work.

EDIT: Ok sorry, re-reading your question I see you just want to know how to do it using recursion. Maybe you'd like to make that clear in the title itself ;-)

Upvotes: 1

SimonC
SimonC

Reputation: 6718

If recursion really is a requirement, and you just need the range, then this should do it:

public static int range(int [] array, int index, int min, int max)
{
    if (index == array.length) {
        if (index == 0)
            return 0;
        else
            return max - min;
    }
    else {
        int value = array[index];
        return range(array, index + 1, Math.min(value, min), Math.max(value, max));
    }
}

public static int range(int [] array)
{
    return range(array, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
}

Upvotes: 2

Andreas
Andreas

Reputation: 313

You could provide a int[] with min (index 0) and max (index 1) within the method and do all in the same method.

public class Test {

@org.junit.Test
public void test() {

    int[] array = new int[] { -5,2,4,6,-10,44};
    int[] minmax = new int[ 2 ];
    minmax( array, minmax, 0 );

    assertEquals( "[-10, 44]", Arrays.toString( minmax ) );
}

public static void minmax(int[] array, int[] minmax, int N) {
    if (N >= array.length) {
        return;
    } else {
        minmax(array, minmax, N + 1);
        if (array[N] < minmax[0]) {
            minmax[0] = array[N];
        } 
        if (array[N] > minmax[1]) {
            minmax[1] = array[N];
        } 
    }
}

}

Upvotes: 0

Bob Brinks
Bob Brinks

Reputation: 1392

You could for example return an array (0 would have min and 1 have max) that way you can return both values.

A nicer way would be to pass a callback function to you method and call that once done.

findMinMax(array, (min, max) -> { System.out.println(min + " " + max);});

private void findMinMax(int[] array, BiFunction<Integer, Integer, Void> callback) {
    //Do things
    callback.apply(min, max);
}

Upvotes: -1

Related Questions