首页 文章

Java递归函数

提问于
浏览
0

我还不太了解递归,我有一些我无法解决的功课 . 有没有人有想法?

任务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 回答

  • 3

    对于一般的递归,您需要以下结构:

    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[] tail(int[] list) ,使用 Arrays.copyOfRange()

    此实现不处理零长度输入列表 - 它将是一个无意义的调用,具有未定义的结果 . 如果你愿意,你可以让它抛出一个更具信息性的例外 .


    你的第二个任务可以用基本相同的方式编写,除了现在有两个“简单”的情况我们不会递归:

    • 如果输入列表为空,答案是 false

    • 如果输入列表的第一个元素是我们正在寻找的,答案是 true

    • 否则它's not '容易',所以递归 .

    所以:

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

    您需要再次使用 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中实现此功能的有效方法 . 但我相信你的老师正在指导你进行更实际和必要的递归应用 .

相关问题