Divide and conquer average

Question

To start with, the problem is not directly with the algorithm (at least I think I got it); the problem shows whenever I use the function that finds the average.

The code compiles but when I get to the line in which said function executes, the program stops working, maybe because of how I'm playing with arrays, or maybe because of how long it takes to execute (although I highly doubt it's the last one).

If someone could please tell me where the problem is:

So, for the program: Try to get the average of an array using divide and conquer. I divide the array by two, then proceed until I only have 1 element of the array and return that value, else, return (avg(lefmost part of the array) + avg(rightmost part of the array))/2.

#include <stdio.h>
#include <stdlib.h>

int avg(int in, int end, int* a){
    if ((end - in) == 0){
        return a[end];
    }
    return (avg(in, ((end - in)/2)-1, a) + avg((end - in)/2, end, a));
}

int main(){
    int a,*b,i;
    printf("Please say how long the array is going to be: ");
    scanf("%d",&a);
    b = (int*)malloc(sizeof(int) * a);
    if (b){
        for(i=0; i<a; ++i){
            printf("Please enter the element number %d of the array: ", i+1);
            scanf("%d",&b[i]);
        }
        printf("The array is:\n\n{\n");
        for(i=0; i<a; ++i){
            printf(" %d\n", b[i]);
        }
        printf("}\n\n");
        printf("The array's average is : %d", avg(0, a-1,b));
    }
    else{
        printf("Sorry, but an array of that size can't be created!\n");
    }

    return 0;
}

That is a terrible way to try to take the average. Recursion is utterly inappropriate here. Just add the numbers, then divide by the count. If you want to do it recursively, then you need to weight the values by their relative counts, then divide by the total (so you are doing a lot more divides). For instance, if you have 7 numbers, and you average the first 4 as a4 and the last 3 as a3, you cannot simply use (a4+a3)/2. Instead, you would need to do (4*a4+3*a3)/7. That is because a4 contains more samples, and thus needs to have a higher weight than a3. Do the math. — Tom Karzes
I know it's a terrible way to find the average, but I was told to find it using this method (mandatory). — Yoakain
if ((end - in) == 0){ is a funny (funny peculiar, that is) way of writing if (end == in) {. — Jonathan Leffler

James Campbell James Campbell · Accepted Answer · 2017-10-07T23:44:25

At first glance, you haven't handled the case of a 2 element array. If in=0 and end=1, then it'll call avg(-1,0,a) ... since with integers, 1/2=0.

Divide and conquer average

1 Answers