0

I wrote the below program to find the sum of all integers using divide and conquer recursion algorithm in Java:

But somehow the sum is coming incorrectly.

public class DivideAndConquerSum {
 public static void main(String[] args) {
    int[] arr = new int[]{2, 3, 4, 5};
    System.out.println(calculateRecursiveSum(arr, 0, arr.length));
  }
  static long sum = 0;
  static long calculateRecursiveSum(int[] arr, int low, int high) {
    if (high == low) {
      return arr[0];
    } else {
      int mid = (high + low) / 2;
      sum = calculateRecursiveSum(arr, low, mid) +
            calculateRecursiveSum(arr, mid + 1, high);
    }
    return sum;
  }
}

Can anyone please let me know what is wrong in the code to resolve it? Assuming only positive integers in this scenario.

Improve this question
3
  • I see what's wrong, and if you step through this in a debugger, you'll see too
    – ControlAltDel
    Commented Mar 17, 2020 at 16:16
  • 1
    The issue with binary chop type constructions is whether the high parameter is the index of the last item to be included in the sum, or the last +1. In this case, starting with high = arr.length says it's last +1, but that's not consistent with the sum = .... recursion, which misses out arr[mid]. If high was the last item to be included in the sum, return arr[0] would need to be return arr[low], but everything else then works as is -- except you start with arr.length - 1 of course, and you need to watch out for arr.length == 0. It's the old "out by 1" gotcha.
    – Chris Hall
    Commented Mar 17, 2020 at 19:22
  • Noted @ChrisHall. Thank you very much for pointing out the nuances.
    – VijayC
    Commented Mar 18, 2020 at 4:35

2 Answers 2

Reset to default
2

Your method basically recalculates mid so you need to return the value at that point. It is more suited to a binary search. But make the following changes and it will work.

       static long calculateRecursiveSum(int[] arr, int low, int high) {
          if (high == low) {
                return 0;
            }
            int mid = (high + low) / 2;
            return arr[mid] + calculateRecursiveSum(arr, low, mid) + 
                      calculateRecursiveSum(arr, mid+1, high);
       }
Improve this answer
3
  • That's a terrible miss from my side. Thank you very much. Just curious to know is there any other way to achieve the same instead of "binary search-ish" way of doing it?
    – VijayC
    Commented Mar 17, 2020 at 16:43
  • Not really. Except for simple recursive routine that sums them up linearly. The issue is that you need to cater to both an even and odd number of values. And your method did that.
    – WJS
    Commented Mar 17, 2020 at 17:16
  • Sure. Thank you very much.
    – VijayC
    Commented Mar 17, 2020 at 17:19
0

Your approach was almost okay, here I corrected few problems to keep your idea working.

public class DivideAndConquerSum
{
   public static void main(String[] args)
   {
      int[] arr = new int[] { 2, 3, 4, 5 };
      System.out.println(calculateRecursiveSum(arr, 0, arr.length - 1));
   }

   // static long sum = 0;
   static long calculateRecursiveSum(int[] arr, int low, int high)
   {
      // long sum=0;
      if (high == low)
      {
         return arr[low];
      }
      else
      {
         int mid = (high + low) / 2;
         return (calculateRecursiveSum(arr, low, mid) + calculateRecursiveSum(arr, mid + 1, high));
      }
      // return sum;
   }
}

You don't need an extra static variable to store the result. Returning the recursive call directly will do it for you.

Improve this answer
1
  • Yep. Thank you very much.
    – VijayC
    Commented Mar 18, 2020 at 4:36

Not the answer you're looking for? Browse other questions tagged or ask your own question.