Java递归函数

Question

我还不太理解递归，我有一些作业我不能解决。有人有主意吗？

任务1：实现一个int方法max（int[]arr，int i），该方法返回arr中所有元素的最大值和索引

这是我迄今为止的代码：

private static int max = 0;

private static int max(int[] arr, int i) {
    if (i >= 0 && i < arr.length) {
        if (arr[i] >= max) {
            max = arr[i];
        }

        max(arr, i - 1);
    }
    return max;
}

实际上它是有效的，但它的风格很差，所以我的问题是：如果没有私有静态int max，我如何实现递归方法？我不允许向该方法添加第三个参数。

任务2：实现一个布尔方法包含值（int[]arr，int val），如果arr的一个元素与val匹配，则返回true。该方法应该有两个递归调用：一个搜索数组的前半部分，另一个搜索后半部分。您可以使用rrays.copyOfRange（...）。

这是我的代码：

private static boolean containsValue(int[] arr, int val) {
    if (arr.length > 1) {
        if (arr[arr.length - 1] == val) {
            return true;
        }
        return containsValue(Arrays.copyOfRange(arr, 0, arr.length-1), val);
    }

    return false;
}

这也行得通，我理解为什么，但显然该方法没有两个递归调用。每次尝试实现将数组分成两半的方法都是一次巨大的失败。有人能帮我吗？

Answer 1

对于一般的递归，您需要以下结构：

if the problem is simple enough to answer easily:
   return the answer
else:
   split the problem into two parts
   recurse to get the answer
   return the answer

对于max（）这是：

if the input list is of size 1:
   return the only element of the list
else
   split the list into a head (first element) and a tail (rest of the list)
   recurse to get the max of tail
   return the head or the max of tail, whichever is largest

或在Java中：

int max(int[] list) {
   if(list.length == 1) {
        return list[0];
   } else {
        return Math.max(list[0], max(tail(list)));
   }
}

（你将需要实现int[]尾巴（int[]列表）自己，使用rrays.copyOfRange（））

此实现不处理长度为零的输入列表——这将是一个无意义的调用，结果未定义。如果您愿意，可以让它抛出一个信息更丰富的异常。

你的第二个作业可以用基本相同的方式编写，只是现在有两个“简单”的情况，我们不会重复：

• 如果输入列表为空，则答案为false

因此：

boolean contains(int value, int[] list) {
   if(list.length == 0) {
        return false;
   } 

   if(list[0] == value) {
      return true;
   }

   return contains(value, tail(list));
}

... 除了告诉你递归到数组的前半部分，然后是后半部分。所以，按照别人告诉你的去做：

int contains(int value, int[] list) {
   if(list.length == 0) {
      return false;
   }

   if(list.length == 1) {
       return list[0] == value;
   }

   return contains(value, firstHalf(list)) || 
          contains(value, secondHalf(list));
}

您需要编写自己的firstHalf（）和secondHalf（）实现，再次使用数组。copyOfRange（）。确保当输入列表的长度为奇数时，中间值仅在其中的一半中。

注意这是多么的声明性——它几乎直接翻译成了一个英语语句：“我知道如果列表是空的，它就不在那里。如果它是列表的第一个元素，或者如果列表的尾部包含它，它就在那里。”

请注意，在这两种情况下，递归都不是Java实现此功能的有效方法。但是我相信你的老师正在指导你更实际和必要的递归应用。