如何在增加索引后递归添加？

Question

我目前正在做家庭作业，目标是只递归地做这个（没有循环）。我很确定我可以重载并添加辅助方法，这是我能看到自己完成此操作的唯一方法。

所以问题是，我有一个整数数组 A = {1,2,3,4}（或类似的东西），我需要用 {10,9 创建一个 returned 数组,7,4}

10 = 1+2+3+4

9 = 2+3+4

7 = 3+4

4 = 4

我想过使用这样的东西（不是工作代码）

int counter = 0;
public int[] r(int[] numbers){
    return r(number, counter);
}

public int[] r(int[] numbers, int index){
    int sum = 0;
    // base case to check if next value exists otherwise end it
    
    // this would be a helper method instead of a for loop
    for(int x=index; x<numbers.length; x++){
        sum += numbers[x];
    }
    
    numbers[index] = sum;
    index++;
    return r(numbers, index);
}

但是，我不确定该怎么做。这也是我使用递归的第一周，所以这让我有点困惑。我得到了正确的数组，但我在 numbers[index] = sum 和我的 return 语句 return r(numbers, index) 上有一个 ArrayIndexOutOfBoundsException，我不确定如何修复它。有什么想法吗？

Answer 1

你的功能不正确

public int[] r(int[] numbers, int index){

    //--> needs a stop condition e.g. index==numbers.length, index==0

    int sum = 0;
    // base case to check if next value exists otherwise end it

    // this would be a helper method instead of a for loop
    for(int x=index; x<numbers.length; x++){
        //--> numbers has been overwritten by the sum 
        // you should just do numbers[index] = numbers[index-1]+numbers[index]
        // this is opposite to the summation you wish for which starts adding 
        // from the last position
        sum += numbers[x];
    }


    numbers[index] = sum;
    index++;
    return r(numbers, index);
}

你的函数的正确解是

public int[] r(int[] numbers, int index){

    if (index == 0) {
          return numbers;
    }else{
        numbers[index] = numbers[index+1] + numbers[index]
        return r(numbers,index-1);
    }

    public int[] r(int[] numbers){
        return r(numbers, numbers.length);
    }

但是你丢失了初始数组，因为你覆盖了它

或

你可以像这样构建一个函数

public int sumRecursive(int[] input, int[] output,int pos){
    if (pos==0){
        output[pos] = input[pos]
        return input[pos]
    }else{
        output[pos] = input[pos] + sumRecursive(input,output,pos-1);
        return output[pos];
     }
}

你需要这样称呼它

int[] output = new int[input.length];
sumRecursive(input,output,input.length);

Answer 2

您需要一个停止条件，以及之后检索数组的方法

public int sum(int old, int[] numbers, int index) {
    if (index == numbers.length) return old;
    return sum(numbers[index] + old, numbers, index + 1);
}

public int[] r(int[] numbers, int[] output, int count) {
    if (count == numbers.length) {
        return output;
    } else {
        output[count] = sum(0, numbers, 0);
        return r(numbers, output, count + 1);
    }
}

public int[] r(int[] numbers) {
    return r(numbers, new int[numbers.length], 0);
}

编辑：更改代码以消除 for 循环

的需要

Answer 3

我想这会给你正确的答案：

public static int[] slideAndSumArrayElements(int[] array, int[] result, int index) {
    // base case - stop when the index is same as the array.length
    if (index == array.length) {
        return result;
    } 
    else {
        // Add all elements of the array starting from the index position till length of the array and store the result in result[index]
        result[index] = addArrayElementsRecursively(array, index);

        // slide the main array by incrementing the index 
        return slideAndSumArrayElements(array, result, index + 1);
    }
}

public static int addArrayElementsRecursively(int[] arr, int index){
    // base case - when the index is same as the original array len stop
    if (arr.length == index){
        return 0;
    }

    // add progressively each element of the given array 
    return arr[index] + addArrayElementsRecursively(arr, index + 1);
}

public static void arraySum(){
    int[] array = {1, 2, 3, 4};
    int[] result = new int[array.length];

    result = slideAndSumArrayElements(array, result, 0);
}

输出数组或结果将是： [10, 9, 7, 4]

如何在增加索引后递归添加？

How to recursively add after increasing index?

java

arrays

recursion

overloading

helper