Binary Recursive Sum of Integer Array in Java

Binary recursion is one of the common methods where inside the current method two recursive method calls are being made to itself recursively.

Sum of all the elements of an integer array can be achieved by using binary recursion.

Binary recursion can be applied to sum elements of an array as follows :

Sum the elements in the first half recursively and sum the elements in the second half recursively. Then add this two sums to find the total sum.

Space complexity = O(logN)
Time complexity = O(N)

public class BinaryRecursiveSumOfArray {

    public static int binaryRecursiveSum( int[] data, int low, int high )
    {  
       if( low>high )
         return 0;
       else if( low == high )
         return data[low];
       else
       {
         int mid = (low+high)/2;
         return binaryRecursiveSum(data, low, mid)+binaryRecursiveSum(data, mid+1, high);
       }
    } 
 
    public static void main(String[] args) {
 
        int[] data =  {1,2,3,4,5,6,7,8};
  
        int result = binaryRecursiveSum(data, 0, data.length-1);
  
        System.out.println(result);  
    }
 
}

For an 8 element array following recursion trace is obtained.

Reference :  http://www.amazon.com/Data-Structures-Algorithms-Java-Edition-ebook/dp/B00JDRQF8C