Odtnhj

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));