Q:

Modifying Summation using Recursion

How do I modify the summation method using recursive definition to get the sum of 1 to N via - (1 to N/2) + ((N/2+1) to N)?
I'm confused a bit here, I've typed out something along the lines of this, but it's not recursion:
public static int Sum(int n){
    int sum1 = 0;
    int sum2 = 0;
    int totalSum = 0;
    for(int i = 1; i <= n/2; i++){
        sum1 += i;
    }
    for(int i = n/2 + 1; i <= n; i++){
        sum2 += i;
    }
    totalSum = sum1 + sum2;
    return totalSum;
}

A:

First off, your implementation is not recursive.
Your question states the right algorithm: to sum the values between 1 and n, you can sum them between 1 and n/2, then between n/2 + 1 and n. This means we need to create a helper function sum(int a, int b) whose goal will be to return the sum of all the values between a and b.

The base case is when a == b: in this case, the helper should just return a.
In the recursive step, we do the previous algorithm: sum from a to (a+b)/2 and sum from (a+b)/2 + 1 to b.

This would be an implementation:
public static int sum(int a, int b) {
    if (a == b) {
        return a;
    }
    int middle = (a + b) / 2;
    return sum(a, middle) + sum(middle + 1, b);
}

with this, the initial task becomes:
public static int sum(int n) {
    return sum(1, n);
}

Some samples:
public static void main(String[] args) {
    System.out.println(sum(4)); // prints 10
    System.out.println(sum(5)); // prints 15
    System.out.println(sum(6)); // prints 21
}

