使用列表递归查找最大值

Question

我正在尝试编写的这个方法在列表中查找整数的最大值，并且对于我必须使用递归的赋值。我想我理解递归的概念，但是用列表或数组来做是我不理解的。是否总是需要将列表或数组分成两半？无论如何，此代码将编译，但我在下面评论的一行中收到 IndexOutOfBounds 错误。它看起来和我应该做的很接近吗？

public static final int findMaxRecursively(List<Integer> numbers) {
int max = 0;

     if(numbers.size() == 1)
       return numbers.size();

     List<Integer> bottomHalf = new ArrayList<Integer>(numbers.size()/2);
     for (int i= 0; i<numbers.size()/2;i++){
         if (bottomHalf.get(i) > max) // here's where the IndexOutOfBounds error occurs
          max = bottomHalf.get(i);
          }
          findMaxRecursively(bottomHalf);

     List<Integer> topHalf = new ArrayList<Integer>(numbers.size()/2);
     for(int i = numbers.size()/2; i< numbers.size(); i++){
         if (topHalf.get(i) > max)   
         max = topHalf.get(i);
    }
         findMaxRecursively(topHalf);

         return max;
}

Answer 1

您的递归调用毫无意义，因为您传递给它们的是空列表，即使它们 returned 了正确的值，您也没有对 returned 值做任何事情。

为了以递归方式找到最大元素，您应该拆分列表。最有效的拆分是分成两个相等的部分。

通过 new ArrayList<Integer>(numbers.size()/2) 创建列表不会将原始列表的一半元素复制到此列表。它只是创建一个空列表，其初始容量是原始列表大小的一半。您可以使用 List<E> subList(int fromIndex, int toIndex); 来查看列表的一部分。

而当 numbers.size() == 1 时，您应该 return numbers.get(0) 而不是 numbers.size()。

最后，使用 for 循环违背了递归解决方案的目的。在递归解决方案中，您只需进行 2 次递归调用以获得下半部分和上半部分的最大值，然后比较两个 returned 值和 return 较大的值。

public static final int findMaxRecursively(List<Integer> numbers) 
{
     if(numbers.size() == 1)
         return numbers.get(0);

     List<Integer> bottomHalf = numbers.subList(0,numbers.size()/2);
     int bottom = findMaxRecursively(bottomHalf);

     List<Integer> topHalf = numbers.subList(numbers.size()/2,numbers.size());
     int top = findMaxRecursively(topHalf);

     return top>bottom?top:bottom;
}

使用列表递归查找最大值

find maximum value recursively with a List

java

recursion

list