Среднее число целых чисел, использующих divide и conquer

Question

Учитывая последовательность целых чисел, как я могу найти среднее значение с помощью подхода divide and conquer? Я должен написать метод «double avg (int [] a, int l, int r)», который находит среднее значение в массиве A, охватывающее от «l» до «r» в качестве домашней работы, но я получаю StackOverflowError на первый рекурсивный вызов - не во втором, хотя! - моего кода, и я не могу понять, почему. Кроме того, я уверен, что это не дает мне истинного среднего значения, но я не нашел возможности проверить среднее значение последовательности, используя разделение и победить. Вот мой код:

public class Average { 
public static void main(String[] args) { 

    int[] A = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}; 
    int l = 0; 
    int r = A.length-1; 
    System.out.println("Average of the array: "+averageCheck(A, l, r)); 

} 

public static double averageCheck(int[] A, int l, int r) { 
    if (l==r) { 
     return A[l]; 
    } 
    // Base Case: if there's just a single element it is the average of the array itself 

    int mid = (l+r)/2; 
    double avLeft = 0; 
    double avRight = 0; 

    avLeft = A[l]/r + averageCheck(A, l, mid); 
    avRight = A[mid+1]/r + averageCheck(A, mid+2, r); 

    double average = ((avLeft*mid) + (avRight * (r-mid))) /r; 

    return average; 

    } 
} 

Answer 1

Ваш рекурсии не заканчивается, когда r == l + 1. В этом случае mid == l и во втором рекурсивном вызове mid+2 будет больше, чем r. Добавьте это в начале функции:

if(l > r) 
     return 0; 

примера, представьте l == 5 и r == 6, то mid будет иметь значение 5. Второй вызов будет averageCheck(A, 7, 6), как это mid+2 7. В этом вызове, условие будет l == r be false. Продолжайте в той же логике, и вы обнаружите, что рекурсия не закончится.

Я также думаю, что было бы лучше, если бы вы вычислили сумму рекурсивно и разделили на длину в конце.

Я полагаю, это решение:

public class Average { 
public static void main(String[] args) { 

    int[] A = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}; 
    System.out.println("Average of the array: "+average(A)); 

} 

public static double average (int[] A) { 
     return averageCheck(A, 0, A.length - 1)/A.length; 
} 

public static double averageCheck(int[] A, int l, int r) { 

if (l > r) 
    return 0; 

if (l==r) { 
    return A[l]; 
} 
// Base Case: if there's just a single element it is the average of the array itself 

int mid = (l+r)/2; 
double avLeft = 0; 
double avRight = 0; 

avLeft = averageCheck(A, l, mid); 
avRight = averageCheck(A, mid+1, r); 

double average = avLeft + avRight; 

return average; 

} 
}