Recursive function that finds the minimum value in an ArrayList of Integers in Java

user_8070604 0
Viewed 1140

This is a problem that I have been thinking about as part of self-learning java. The problem consists of writing a recursive function that finds the minimum value in an ArrayList of Integers. Below you will find my attempt. I believe that it is working as intended, but I wonder if there are better ways to get this done. Any comments are appreciated.

public static int findMin(ArrayList<Integer> numbers){
        // Base Case
        if(numbers.size()==1){
            return numbers.get(0).intValue();
        }
    
  
        ArrayList<Integer> numbers_short = new ArrayList<Integer>(numbers);
        numbers.remove(numbers.size()-1);

        return Math.min(numbers_short.get(numbers_short.size()-1).intValue(), findMin(numbers));
    }
minimum arraylist integer java
3 Answers

Your example is not so good in the way that you should not use recursivity in this case. But anyway, you can avoid to copy your array each time, by using a method with a start and end parameters to analyze only a part of your initial array.

Something like that:


    public static int findMin(ArrayList<Integer> numbers) {
        return findMin(numbers, 0, numbers.size() - 1);
    }

    public static int findMin(ArrayList<Integer> numbers, int start, int end) {
        if (end == start)
            return numbers.get(start);
        int middle = start + (end - start) / 2;
        return Math.min(findMin(numbers, start, middle), findMin(numbers, middle + 1, end));
    }

And add a check in case the array is empty if needed.

The reason why I'm using the "middle" method is that each time it divides the array by 2, meaning at the end it limits the risk of stack overflow because it will divide by 2 the maximum number of recursivity compare to recurse on every element.

user_147433900

You may want to avoid creating a new ArrayList object every time you call the method. This may seem non consequential for smaller inputs, but for really large inputs it may lead to StackOverflowError.

A cleaner solution with similar time complexity can be:

public static int findMin(ArrayList<Integer> numbers) {
        return findMin(numbers, numbers.size());
    }

public static int findMin(ArrayList<Integer> numbers, int len) {
    // Base Case
    if (len == 1) {
        return numbers.get(0);
    }
    
    return Math.min(numbers.get(len-1), findMin(numbers, len-1));
}

Reference to garbage collector and recursion: Garbage Collection in Java with Recursive Function

user_63952620

Keeping the original method signature and formal parameters - the code can be simplified by eliminating the need to create a new temporary array each time.

public static int findMin(ArrayList<Integer> numbers){
        if (numbers.size() == 1) return numbers.get(0);
        return Math.min(numbers.remove(0), findMinimum(numbers));
    }

numbers.remove(0) will simultaneously remove the first element and return the value of the removed element, eliminating the need to create a temporary array.

user_178680840
Related