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

Reverse Integer Array Recursively in Java

Recursion can be used to reverse an integer array without allocating a new array.

This method is more space efficient than the solution which creates a new array to hold the reversed one.

By starting from the specific start index to end index inclusively, following method enables to reverse items at specific array index recursively.

public class ReverseArray {

 public static void reverseArray( int[] data, int low, int high )
 {
  if( low<high )
  {
   int temp = data[low];
   data[low] = data[high];
   data[high] = temp;
   reverseArray(data, low+1, high-1);   
  }  
 }
 
 public static void main(String[] args) {
  
  int[] arr = {4,3,6,2,7,8,9,5};
  
  for (int i = 0; i < arr.length; i++) {
   
   System.out.print(arr[i]+" ");   
  }
  
  System.out.println();
  
  reverseArray(arr, 1, 3);
  
  for (int i = 0; i < arr.length; i++) {
   
   System.out.print(arr[i]+" ");   
  }  
  
 }
}

Sample input and output arrays can be used :

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

Recursive Sum of the First n Elements of an Array in Java

We assume that input is a non-zero length integer array.

Base case (Termination condition) : if n == 0 then return 0

General case : return the sum of the first n-1 integers in the array plus the value at the specified index in the array

For the input array {1, 3, 5, 4, 7} find the sum of the first 4 items in the array recursively.

Result is the sum of the items =  1+3+5+4=13

public class SumOfNIntegers {

 
 public static int recursiveArraySum(int[] data, int n)
 {
  if( n==0 )
   return 0;
  else
   return recursiveArraySum(data, n-1) + data[n-1];
 }
 
 public static void main(String[] args) {
  
  int[] inputArray = {1, 3, 5, 4, 7};
  
  int result = recursiveArraySum(inputArray, 3);
  
  System.out.println(result);
  
  result = recursiveArraySum(inputArray, 4);
  
  System.out.println(result);
  
 } 
}

recursiveArraySum method takes input array and the number of items to sum from the beginning of the array.

Console output is :

9

13


Diagram for the recursive method calls :

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