我还不太了解递归,我有一些我无法解决的功课 . 有没有人有想法?
任务1:实现一个int方法max(int [] arr,int i),它返回索引<= 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:实现一个布尔方法containsValue(int [] arr,int val),如果arr的一个元素匹配val,则返回true . 该方法应该有两个递归调用:一个搜索数组的前半部分,另一个搜索后半部分 . 您可以使用Arrays.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;
}
这也有效,我理解为什么,但显然该方法没有两个递归调用 . 每次尝试实现将阵列分成两半的方法都是一个巨大的失败 . 谁能帮我?
1 回答
对于一般的递归,您需要以下结构:
对于
max()
,这是:或者在Java中:
(你需要自己实现
int[] tail(int[] list)
,使用Arrays.copyOfRange()
)此实现不处理零长度输入列表 - 它将是一个无意义的调用,具有未定义的结果 . 如果你愿意,你可以让它抛出一个更具信息性的例外 .
你的第二个任务可以用基本相同的方式编写,除了现在有两个“简单”的情况我们不会递归:
如果输入列表为空,答案是
false
如果输入列表的第一个元素是我们正在寻找的,答案是
true
否则它's not '容易',所以递归 .
所以:
...除了你被告知进入前半部分,然后是阵列的后半部分 . 所以,就像你被告知的那样:
您需要再次使用
Arrays.copyOfRange()
编写自己的firstHalf()
和secondHalf()
实现 . 确保当输入列表为奇数长度时,中间值仅为一半 .请注意这是如何声明的 - 它几乎直接转换为英语声明:"I know it's not there if the list is empty. It's there if it's the first element of the list, or if the tail of the list contains it."
请注意,在这两种情况下,递归都不是在Java中实现此功能的有效方法 . 但我相信你的老师正在指导你进行更实际和必要的递归应用 .