Блог

Главная - Вопросы по программированию - Привязка к индексу при рекурсивном суммировании массива пополам

Привязка к индексу при рекурсивном суммировании массива пополам

#java #recursion

#java #рекурсия

Вопрос:

Я практиковался в рекурсии, и одно из упражнений, которое я пытаюсь выполнить, — это получить сумму массива, разделив его пополам, а затем перейти к одному элементу и добавить его значение в накопитель, который будет возвращен.

Код:

 public static int arrayValuesSum(int[] arr) {
    return arrayValuesSumHelper(arr,0);
}

public static int arrayValuesSumHelper(int[] arr, int acc) {
    if (arr.length == 0)
        acc  = 0;

    else if (arr.length == 1)
        acc  = arr[0];

    else if(arr.length == 2) {
        int[] arrOne = new int[] {arr[0]};
        int[] arrTwo = new int[] {arr[1]};
        return arrayValuesSumHelper(arrOne, acc)   arrayValuesSumHelper(arrTwo, acc);
    }

    else {
        int[] arrOne = Arrays.copyOfRange(arr, arr[0], arr[(arr.length/2)]);
        int[] arrTwo = Arrays.copyOfRange(arr, arr[((arr.length)/2)], arr[(arr.length)]);
        return arrayValuesSumHelper(arrOne, acc)   arrayValuesSumHelper(arrTwo, acc);
    }
    return acc;
}

Однако, когда размер массива больше двух, я получаю indexOutOfBounds исключения, и я знаю, что copyofRange(int startInc, int endExc) это [a, b). Я много с этим играл. Почему это не работает? Как с размерами массива, имеющими только четные множители, так и без них?

Комментарии:

1. Исключение точно подскажет вам, что не так и в какой строке кода. Используй это!

2. Я пытался поставить точку останова в @john3136, но мне нужна помощь! Иначе меня бы здесь не было.

3. вам не нужна точка останова. Вы сказали, что получили исключение IndexOutOfBounds. Это покажет вам строку кода, индекс, к которому вы пытались получить доступ, и максимально допустимый индекс. Это все, что вам нужно, чтобы выяснить, что происходит.

Ответ №1:

Моя рекомендация в отношении рекурсии — упростить ее и позволить рекурсии выполнять всю работу. Это прекрасный пример. Вы сделали решение слишком сложным и преследуете ошибки, которых даже не должно было произойти. Рассмотрим:

 public static int arrayValuesSum(int[] array) {
    return arrayValuesSumRecursive(array, 0, array.length);
}

public static int arrayValuesSumRecursive(int[] array, int start, int length) {

    if (length == 0)
        return 0;

    if (length == 1)
        return array[start];

    int half = length / 2;

    return arrayValuesSumRecursive(array, start, half)   arrayValuesSumRecursive(array, start   half, length - half);
}

Нет необходимости тратить время и пространство на копирование и повторное копирование массива.