Vfrdtyky

So I am attempting to get my head around the divide and conquer principle and multiple recursive calls in a single method. It's going ok but I have a problem with the output of the method I am writing.

The purpose of the method is to return the sum of all the pairs of consecutive numbers in an array. I am 95% there but am not getting the output I expect and have been banging me head against the desk for ages trying to work out why.

The array is:

int array = { 11, 6, 87, 32, 15, 5, 9, 21 };

and the method is:

public int consecutivePairsSum_DivideAndConquer(int start, int end, int array) {

    int leftSum;

    int rightSum;

    int middle = (start + end) / 2;

    if (start == middle) {

        return array[middle];

    } else {

        leftSum = array[start] + array[start + 1];

        leftSum += consecutivePairsSum_DivideAndConquer(start, middle, array);

    }

    if (middle == end) {

        return array[end];

    } else {

        rightSum = array[middle] + array[middle+1];

        rightSum += consecutivePairsSum_DivideAndConquer(middle+1, end, array);

    }

    return leftSum + rightSum;

}

Here's my method call:

System.out.println(rF.consecutivePairsSum_DivideAndConquer(0, array.length-1, array));

I think it must be something to do with how I have split the array but no amount of experimenting is giving me the right output.

Expected output: 340

Actual output: 330

Any suggestions most welcome, this is driving me nuts! :p

ps Any useful links to where I can find a solid online tutorial/good book about recursion would also be great (if that's within the scope of SO seeing how it's not direct help with a programming issue)

Here's an outline of the algorithm:

Base case: If your array has less than two elements, the result is 0 (because there are no pairs).

Otherwise: Divide the array into two halves, calculate the results for left and right halves, then the result for the whole array would be <result of left half> + <result of right half> + <last element of left half> + <first element of right half> (Because the only pair missing here is the pair at the location of the split).

In java, it would be something like this:

int consPairSum(int array, int left, int right) {

    if(right <= left + 1) return 0;



    int mid = (left + right) / 2;

    int leftPairSum = consPairSum(array, left, mid);

    int rightPairSum = consPairSum(array, mid, right);

    return leftPairSum + rightPairSum + array[mid - 1] + array[mid];

}

It should be called as

consPairSum(array, 0, array.length);

who said divide and conquer needs to divide into equal chunks you just need to divide into self similar problem. almost 1 liner.

static private int doTheThing(int list){

    if (list.length==2)

        return list[0]+list[1];

    return list[0]+list[1]+doTheThing(Arrays.copyOfRange(list,1,list.length));

}