Fredrik Jönsson Fredrik Jönsson - 3 months ago 10
Java Question

Calculating sum 1 to N by adding 1 to N/2 with N/2 to N in a recursive method

I am having trouble making a recursive method that calculates the sum of 1,2,3 to N, but does it by adding (1,2,3... to N/2) with (N/2+1... to N).

The code i manage so far is this:

public static void main(String[] args) {

System.out.println(sum(10, 1));
}

public static int sum(int n, int start) {

if (start == n){
return n;
}

if (start > n / 2){
return start + sum(n, start + 1);
}

return start + sum(n, start + 1);

}


I believe this is wrong, It is an assignment in school where we have to motivate how splitting the recursion up into to parts is a more/lesser efficient way of calculating the sum. (adding numbers from 1 to N/2 with N/2 to N, instead of just from 1 to N directly).

He made us do this way to make it harder for us but i cannot grasp the idea on how to do this at all. Is it correct?

Thanks

Answer

Might be helpful in some cases to reduce recursion depth.

You need to take start into account when calculating n/2 for inner steps, the code should probably look similar to this:

public static int sum(int n, int start) {
  if (start > n) {
    return 0;
  }

  if (start == n){
      return n;
  }

  int n2 = (start + n) / 2;
  return sum(n2, start) + sum(n, n2 + 1);
} 

The start > n check just avoids extra checks at the end for the case where start and n are less than 2 apart.