Average of a sequence of integers using divide and conquer

Question

Given a sequence of integers, how can I find the average of it using a divide and conquer approach? I have to write a method "double avg(int[] a, int l, int r)" that finds the average in the array A, spanning from 'l' to 'r' as homework, but I get a StackOverflowError on the first recursive call - not in the second, though! - of my code, and I can't seem to understand why. Also, I'm pretty sure it doesn't give me a true average, but I found no way to check the average of a sequence using the divide and conquer. Here is my code:

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;

    }
}

(Not the cause of the StackOverflowError) The average of a sequence of integers is the sum divided by the length. Don't do the division until the end. Particularly don't divide by r, that is meaningless. — Andy Turner
Two hints: consider writing unit test - such code is perfect for that. For the exception itself ... that typically means that you created an infinite recursion. Meaning: your code is missing conditions to stop the recursion. So, step one: add print statements for your variables, and/or run it in a debugger. — GhostCat
@AndyTurner, I had read somewhere that the sum of Element/Lenght done for every element is the average, so I thought it was real. I'll try with a normal average now, but it's even harder to imagine it recursively. — Monok
The r stands for "right", not "real", and you are doing integer division also, so don't be surprised if you don't get the exact answer — OneCricketeer
@cricket_007 true that, but I still don't get the average. Am I doing something wrong calculating it? Any idea how to change it, and still use the divide and conquer? — Monok

AhmadWabbi AhmadWabbi · Accepted Answer · 2016-06-15T13:14:55

Your recursivity does not end when r == l + 1. In this case, mid == l and in the second recursive call, mid+2 will be greater than r. Add this at the beginning of the function:

if(l > r)
       return 0;

Example, imagine l == 5 and r == 6, then mid will have the value 5. The second call will be averageCheck(A, 7, 6) as mid+2 is 7. In this call, the condition l == r will be false. Continue in the same logic and you will find that the recursivity will not end.

I think also that it would be better if you calculate the sum recursively and divide by the length at the end.

I suggest this solution:

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;

}
}

Average of a sequence of integers using divide and conquer

1 Answers