Java 使用递归查找数组中的最大值

Finding Max value in an array using recursion

提问by Scarl

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:

对于我被要求解决的问题之一，我使用 for 循环找到了数组的最大值，所以我尝试使用递归找到它，这就是我想出的：

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?

所以它工作正常并获得最大值，但我的问题是：对于基本情况是否可以返回 a[head] 并且对于头部的值是 > 最后的值的情况？

采纳答案by Joost

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

这更好地显示了正在发生的事情，并使用默认的“递归”布局，例如使用公共基本步骤。初始调用是通过执行findMax(a, a.length-1).

回答by azz

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_VALUEwill be returned only on empty arrays. This runs in linear time.

在每个元素上，您返回当前元素中较大的一个，以及具有更大索引的所有元素。Integer.MIN_VALUE只会在空数组上返回。这在线性时间内运行。

回答by AlexWien

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.

其中 a 和 b 是数组索引。

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

停止条件是 when b - a <= 1，那么它们是邻居，最大值是 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).

这将最大递归深度从 N 减少到 log2(N)。
但是搜索工作仍然保持 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);
   }
}

回答by Rock

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.

我觉得使用当前最大值的跟踪器会很好。

回答by Vallabh Patade

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);

回答by Recomer

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;
}

回答by user6694478

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));

    }

回答by rrr

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));
}

回答by Ghulam Moinul Quadir

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;
    }
}

回答by Learnaholic

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);
        }
}