11

For one of the questions i was asked to solve, I found the max value of an array using a for loop, so i tried to find it using recursion and this is what I came up with:

public static int findMax(int[] a, int head, int last) {

    int max = 0;
    if (head == last) {
        return a[head];
    } else if (a[head] < a[last]) {
        return findMax(a, head + 1, last);
    } else {
        return a[head];
    }
}

So it works fine and gets the max value, but my question is : is it ok to have for the base case return a[head] and for the case when the value at the head is > the value at last?

Improve this question
4
  • I basically know how to get the max value using a for loop, so i wanted to try to write out the code using recursion Commented Oct 25, 2013 at 13:19
  • This should fail for the array {2,42,1} if head=0 and last=2, the method would return 2 without recursing. Commented Oct 25, 2013 at 13:49
  • @Ingo it actually returns 42 as a max value..EDIT: nevermind you are right! Commented Oct 25, 2013 at 16:44
  • By that I think I should edit the code from else return head to else return findMax(a,head,last-1) Commented Oct 25, 2013 at 16:47

16 Answers 16

Reset to default
19

You could just as easily do it with only one counter, just the index of the value you want to compare this time:

public static int findMax(int[] a, int index) {
    if (index > 0) {
        return Math.max(a[index], findMax(a, index-1))
    } else {
        return a[0];
    }
}

This much better shows what is going on, and uses the default "recursion" layout, e.g. with a common base step. Initial call is by doing findMax(a, a.length-1).

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Actually, I worked it out with 2 counters in order to keep track of the index..like the head counter will be the one moving towards the end of the array. In your answer, i don't get why you used the Math.max.
Math.max does what your if (a[head] < a[last]) does, essentially. This is basically Divide and Conquer, where you only handle the current index and the result of the rest (the recursive call) and merge them together for the required answer. In this case you want the maximum of them, so you merge with Math.max.
why to check if the index is greater than 0 ? base case can be added first
9

It's actually much simpler than that. The base case is if you've reached the end of the array (the 'else' part of the ternary control block below). Otherwise you return the max of the current and the recursive call.

public static int findMax(int[] a) {
    return findMax(a, 0);
}
private static int findMax(int[] a, int i) {
    return i < a.length
           ? Math.max(a[i], findMax(a, i + 1))
           : Integer.MIN_VALUE;
}

At each element, you return the larger of the current element, and all of the elements with a greater index. Integer.MIN_VALUE will be returned only on empty arrays. This runs in linear time.

Improve this answer

Comments

4

I would solve this by dividing the array in to the half on each recursive call.

 findMax(int[] data, int a, int b)

where a and b are array indices.

The stop condition is when b - a <= 1, then they are neighbours and the max is max(a,b);

The initial call:

 findMax(int[] data, int 0, data.length -1);

This reduces the maximum recursion depth from N to log2(N).
But the search effort still stays O(N).

This would result in 

int findMax(int[] data, int a, int b) {
   if (b - a <= 1) {
     return Math.max(data[a], data[b]);
   } else {
     int mid = (a+b) /2; // this can overflow for values near Integer.Max: can be solved by a + (b-a) / 2; 
     int leftMax =  findMax(a, mid);
     int rightMax = findMax(mid +1, b);
     return Math.max(leftMax, rightMax);
   }
}
Improve this answer

6 Comments

The only optimisation there is that you're decreasing the stack overhead, it's still the same (O(n)) complexity.
Indeed, @DerFlatulator. Because here both sides of the "tree" are visited, all n elements are visited, for O(n). Its resembles of a binary search is misleading, because for binary search only one side of the tree is visited, to reach the deepest element in O(log n) steps, for a balanced tree.
Yes this is the only optimisation, but it increaes the possible array size; But its still a stupid question; they should learn a recursive binary search instead.
@Joost Updated to incorporate your comments.
It doesn't really make sense to search a regular array with recursion, anyway. So attempting to optimise it when you could just switch to an iterative approach seems futile.
|
2

I came across this thread and it helped me a lot. Attached is my complete code in both recursion and divide&conquer cases. The run time for divide&conquer is slightly better than recursion. 

//use divide and conquer.
public int findMaxDivideConquer(int[] arr){
    return findMaxDivideConquerHelper(arr, 0, arr.length-1);
}
private int findMaxDivideConquerHelper(int[] arr, int start, int end){
    //base case
    if(end - start  <=  1) return Math.max(arr[start], arr[end]);
    //divide
    int mid = start + ( end - start )/2;
    int leftMax =findMaxDivideConquerHelper(arr, start, mid);
    int rightMax =findMaxDivideConquerHelper(arr, mid+1, end);
    //conquer
    return Math.max( leftMax, rightMax );
}

// use recursion. return the max of the current and recursive call
public int findMaxRec(int[] arr){
    return findMaxRec(arr, 0);
}
private int findMaxRec(int[] arr, int i){
    if (i == arr.length) {
        return Integer.MIN_VALUE;
    }
    return Math.max(arr[i], findMaxRec(arr, i+1));
}
Improve this answer

Comments

1

What about this one ?

public static int maxElement(int[] a, int index, int max) {
    int largest = max;
    while (index < a.length-1) {
        //If current is the first element then override largest
        if (index == 0) {
            largest = a[0];
        }
        if (largest < a[index+1]) {
            largest = a[index+1];
            System.out.println("New Largest : " + largest); //Just to track the change in largest value
        }
        maxElement(a,index+1,largest);
    }
    return largest;
}
Improve this answer

Comments

1

I know its an old Thread, but maybe this helps!

public static int max(int[] a, int n) {
        if(n < 0) {
            return Integer.MIN_VALUE;
        }
        return Math.max(a[n-1], max(a, n - 2));

    }
Improve this answer

Comments

1 
class Test
{
    int high;
    int arr[];
    int n;
    Test()
    {
        n=5;
        arr = new int[n];
        arr[0] = 10;
        arr[1] = 20;
        arr[2] = 30;
        arr[3] = 40;
        arr[4] = 50;
        high = arr[0];
    }
    public static void main(String[] args)
    {
       Test t = new Test();
       t.findHigh(0);
       t.printHigh();
    }
    public void printHigh()
    {
        System.out.println("highest = "+high);
    }
    public void findHigh(int i)
    {
        if(i > n-1)
        {
            return;
        }
        if(arr[i] > high)
        {
            high = arr[i];
        }
        findHigh(i+1);
        return;
    }
}
Improve this answer

Comments

0

You can do it recursively as follows.

Recurrent relation it something like this.

   f(a,n)   = a[n]   if n == size
            = f(a,n+1) if n != size

Implementation is as follows.

   private static int getMaxRecursive(int[] arr,int pos) {
         if(pos == (arr.length-1)) {
                return arr[pos];
         } else {           
                return Math.max(arr[pos], getMaxRecursive(arr, pos+1));
         }
   }

and call will look like this

      int maxElement = getMaxRecursive(arr,0);
Improve this answer

Comments

0

its not okay! your code will not find the maximum element in the array, it will only return the element that has a higher value than the elements next to it, to solve this problem,the maximum value element in the range can be passed as argument for the recursive method.

    private static int findMax(int[] a, int head, int last,int max) {
    if(last == head) {
        return max;
    }
    else if (a[head] > a[last]) {
            max = a[head];
            return findMax(a, head, last - 1, max);
        } else {
            max = a[last];
            return findMax(a, head + 1, last, max);
        }
}
Improve this answer

Comments

0

Optimized solution

public class Test1 {
    public static int findMax(int[] a, int head, int last) {

        int max = 0, max1 = 0;

        if (head == last) {
            return a[head];

        } else if (a[head] < a[last]) {
            max = findMax(a, head + 1, last);
        } else
            max = findMax(a, head, last - 1);

        if (max >= max1) {
            max1 = max;
        }
        return max1;


    }

    public static void main(String[] args) {
        int arr[] = {1001, 0, 2, 1002, 2500, 3, 1000, 7, 5, 100};
        int i = findMax(arr, 0, 9);
        System.out.println(i);
    }
}
Improve this answer

Comments

0

Thanks @Robert Columbia for the suggestion!

Update: This following function is going to recursively start from index 0 and it will keep adding to this index value till it's equal to the Length of the array, if it's more we should stop and return 0. Once we're doing that, we need to get the max of every two items in the array so, for example:

A = [1 , 2 , 3 ];

A[0] ( 1 ) vs A[1] ( 2 ) = 2 
A[1] ( 2 ) vs A[2] ( 3 ) = 3
Max(2,3) = 3 ( The answer )  





public int GetMax(int [] A, int index)  {

     index += 1;
     if (index >= A.Length) return 0;
     return Math.Max(A[index], GetMax(A, index + 1));

 }
Improve this answer

1 Comment

While this code may answer the question, it is better to explain how to solve the problem and provide the code for reference. Code-only answers tend to be of low utility and can be confusing.
0 
static int maximumOFArray(int[] array,int n) {
    
    
    int max=Integer.MIN_VALUE;
    
    if(n==1) return array[0];
    else
        max=maximumOFArray(array, --n);

    max= max>array[n] ? max : array[n];
    return max;
        
}
Improve this answer

2 Comments

This is a simple recursive solution with no class method calls...........
consider adding an explanation to your answer. Also, It won't work when an empty array supplied
0

private static int getMax(int [] arr, int idx) {

    if (idx==arr.length-1 ) return arr[idx];

    
    return Math.max(arr[idx], getMax (arr,idx+1 ));
}
Improve this answer

Comments

0 
public class FindMaxArrayNumber {

    public static int findByIteration(int[] array) {
        int max = array[0];
        for (int j : array) {
            max = Math.max(j, max);
        }
        return max;
    }

    public static int findByRecursion(int[] array, int index) {
        return index > 0
                ? Math.max(array[index], findByRecursion(array, index - 1))
                : array[0];
    }

    public static void main(String[] args) {
        int[] array = new int[]{1, 2, 12, 3, 4, 5, 6};
        int maxNumberByIteration = findByIteration(array);
        int maxNumberByRecursion = findByRecursion(array, array.length - 1);

        System.out.println("maxNumberByIteration: " + maxNumberByIteration);
        System.out.println("maxNumberByRecursion: " + maxNumberByRecursion);

        // Outputs:
        // maxNumberByIteration: 12
        // maxNumberByRecursion: 12
    }
}
Improve this answer

Comments

0 
public static int finaMax(int[] list) {
    if (list.length == 2) {
        return list[0] > list[1] ? list[0] : list[1];
    }

    int subMAx = finaMax(Arrays.copyOfRange(list, 1, list.length));

    return list[0] > subMAx ? list[0] : subMAx;
}
Improve this answer

1 Comment

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.
-1 
int maximum = getMaxValue ( arr[arr.length - 1 ], arr, arr.length - 1 );

public static int getMaxValue ( int max, int arr[], int index )
{
    if ( index < 0 )
        return max;
    if ( max < arr[index] )
        max = arr[index];
    return getMaxValue ( max, arr, index - 1 ); 
}

I felt that using a tracker for current maximum value would be good.

Improve this answer

2 Comments

At first glance this will only work with arrays of length >= 2.
why is there a length-2 in this proposal?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.