Maximum Contiguous Subsequence Sum in Linearithmic Time Recursively in Java

There are different solutions to maximum subsequence sum problem with varying complexities such as linear, quadratic and cubic.

There is also a linearithmic solution for the maximum subsequence sum problem implemented in Java.

This linearithmic solution is achieved by applying a divide-and-conquer algorithm design strategy.

Algorithm divides the input array into two different parts from the middle and then searches the max sum
1-) in the first half
2-) in the second half
3-) in the sub array that crosses the mid point of the array

1st and 2nd cases are achieved with recursive calls.

3rd case is achieved by as described at :

"by finding the largest sum in the first half that includes the last element in the first half, and the largest sum in the second half that includes the first element in the second half."

package basics;

public class MaxSubSumLinearithmic {

 public static int maxSubSum(int[] inArr) {
  return maxSubSum( inArr, 0, inArr.length-1 );
 }

 public static int maxSubSum(int[] inArr, int left, int right) {

  if (left == right)
   if (inArr[left] > 0)
    return inArr[left];
   else
    return 0;

  int mid = (left + right) / 2;
  int maxLSum = maxSubSum( inArr, left, mid);
  int maxRSum = maxSubSum( inArr, mid+1, right);

  int maxLBorderSum = 0, leftBorderSum = 0;
  for (int i = mid; i >= left; i--) {
   leftBorderSum += inArr[i];
   if ( leftBorderSum > maxLBorderSum )
    maxLBorderSum = leftBorderSum;
  }

  int maxRBorderSum = 0, rightBorderSum = 0;
  for (int i = mid + 1; i <= right; i++) {
   rightBorderSum += inArr[i];
   if ( rightBorderSum > maxRBorderSum )
    maxRBorderSum = rightBorderSum;
  }

  return getMax3( maxLSum, maxRSum, maxLBorderSum+maxRBorderSum );
 }
 
 private static int getMax3( int a, int b, int c )
 {
      return a > b ? a > c ? a : c : b > c ? b : c;
 }

 public static void main(String[] args) {

  int input[] = { -2, -3, 4, -1, -2, 1, 5, -3 };

  System.out.println("Max Sub Array Sum Result = " + maxSubSum(input));

  input = new int[] { -2, 3, -16, 100, -4, 5 };

  System.out.println("Max Sub Array Sum Result = " + maxSubSum(input));

  input = new int[] { -2, 11, -4, 13, -5, 2 };

  System.out.println("Max Sub Array Sum Result = " + maxSubSum(input));

  input = new int[] { -15, -23, -476, -3, -292 };

  System.out.println("Max Sub Array Sum Result = " + maxSubSum(input));
 }
}

Create a MaxSubSumLinearithmic.java file in your workspace.

When the main method inside the MaxSubSumLinearithmic class executed it is going to print :

Max Sub Array Sum Result = 7
Max Sub Array Sum Result = 101
Max Sub Array Sum Result = 20
Max Sub Array Sum Result = 0


References :

Data Structures and Algorithm Analysis in Java (3rd Edition)

Divide and Conquer Solution to Max Sub Sum

Finding-maximum-contiguous-subsequence-sum-using-divide-and-conquer-approach

Max Sub Array Problem Definition from Wikipedia

Finding Maximum of Three Integers in Java

Finding maximum of three integers problem helps to understand if-else branching and conditionals topic in a better way.

Following is the implementation of the find maximum of three integers in Java.

package basics;

public class ThreeComparator {

 public static int max3( int a, int b, int c )
 {
  if( a>b )
  {
   if( a > c )
       return a;
   else
       return c;
  }
  else if( b>c )
  {
                 return b;
  }
  else
  {
   return c;
  }
  
 }
 
 public static void main(String[] args) {
  
  int a = 4;
  int b = 3;
  int c = 5;
  
  System.out.println("Maximum of "+a+" , "+b+" and "+c+" is = "+max3( a,b,c ));
  System.out.println("Maximum of "+a+" , "+c+" and "+b+" is = "+max3( a,c,b ));
  System.out.println("Maximum of "+b+" , "+a+" and "+c+" is = "+max3( b,a,c ));
  System.out.println("Maximum of "+b+" , "+c+" and "+a+" is = "+max3( b,c,a ));
  System.out.println("Maximum of "+c+" , "+a+" and "+b+" is = "+max3( c,a,b ));
  System.out.println("Maximum of "+c+" , "+b+" and "+a+" is = "+max3( c,b,a ));
  
  System.out.println("Maximum of 4 , 5 and 4 is = "+max3( 4,5,4 ));
  System.out.println("Maximum of 41 , 41 and 41 is = "+max3( 41,41,41 ));
  System.out.println("Maximum of 11 , 21 and 31 is = "+max3( 11,21,31 ));  
 }
}

Create a ThreeComparator.java file in your workspace.

When the main method inside the ThreeComparator class executed it is going to print :

Maximum of 4 , 3 and 5 is = 5
Maximum of 4 , 5 and 3 is = 5
Maximum of 3 , 4 and 5 is = 5
Maximum of 3 , 5 and 4 is = 5
Maximum of 5 , 4 and 3 is = 5
Maximum of 5 , 3 and 4 is = 5
Maximum of 4 , 5 and 4 is = 5
Maximum of 41 , 41 and 41 is = 41
Maximum of 11 , 21 and 31 is = 31

Power of a Number Implementation Recursive in Java

Calculation of exponentiation returns the value of the base number a raised to the exponent n.

Following is the recursive implementation of the power method in Java.

package basics;

public class PowerCalculator {

 public static long pow(long base, int n) {
  
  if (n == 0)
      return 1;
  
  if (n == 1)
      return base;
  
  if (n%2==0)
      return pow( base*base, n/2 );
  else
      return pow( base*base, n/2 )*base;
 }

 public static void main(String[] args) {
  
  long base = 2;
  int exponent = 4;
  System.out.println("Result of "+base+" to the "+exponent+" is = "+pow( base, exponent ));
  
  base = 3;
  exponent = 5;
  System.out.println("Result of "+base+" to the "+exponent+" is = "+pow( base, exponent ));
  
  base = 5;
  exponent = 4;
  System.out.println("Result of "+base+" to the "+exponent+" is = "+pow( base, exponent ));
  
 }
}

Create a PowerCalculator.java file in your workspace.

When the main method inside the PowerCalculator class executed it is going to print :

Result of 2 to the 4 is = 16
Result of 3 to the 5 is = 243
Result of 5 to the 4 is = 625


References :

Data Structures and Algorithm Analysis in Java (3rd Edition)

Exponentiation in Wiki

Math pow method

Java 7 Math.pow implementation

For big numbers you can use Java-BigInteger

Greatest Common Divisor GCD Implementation Recursive and Iterative in Java

The greatest common divisor (gcd) of two integers is the largest positive integer that divides the numbers without a remainder.

For example, the GCD of 8 and 12 is 4.

package basics;

public class GCD {

 public static long gcdRecursive(long a, long b) {
  
  if (a == 0)
   return b;
  if (b == 0)
   return a;
  if (a > b)
   return gcdRecursive(b, a % b);
  
  return gcdRecursive(a, b % a);
 }

 public static long gcdIterative(long m, long n) {
  
  while ( m!=0 && n != 0 ) {
   long remainder = m % n;
   m = n;
   n = remainder;
  }
  return m+n;
 }
 
 public static void main(String[] args) {
  
  System.out.println("Recursive GCD of 50 and 0 = "+gcdRecursive(50,0));
  System.out.println("Recursive GCD of 0 and 50 = "+gcdRecursive(0,50));
  System.out.println("Recursive GCD of 50 and 10 = "+gcdRecursive(50,10));
  System.out.println("Recursive GCD of 40 and 9 = "+gcdRecursive(40,9));
  System.out.println("Recursive GCD of 8 and 12 = "+gcdRecursive(8,12));
  System.out.println();
  
  System.out.println("Iterative GCD of 50 and 0 = "+gcdIterative(50,0));
  System.out.println("Iterative GCD of 0 and 50 = "+gcdIterative(0,50));
  System.out.println("Iterative GCD of 50 and 10 = "+gcdIterative(50,10));
  System.out.println("Iterative GCD of 40 and 9 = "+gcdIterative(40,9));
  System.out.println("Iterative GCD of 8 and 12 = "+gcdRecursive(8,12));
 }

}

Create a GCD.java file in your workspace.

When the main method inside the GCD class executed it is going to print :

Recursive GCD of 50 and 0 = 50
Recursive GCD of 0 and 50 = 50
Recursive GCD of 50 and 10 = 10
Recursive GCD of 40 and 9 = 1
Recursive GCD of 8 and 12 = 4


Iterative GCD of 50 and 0 = 50
Iterative GCD of 0 and 50 = 50
Iterative GCD of 50 and 10 = 10
Iterative GCD of 40 and 9 = 1
Iterative GCD of 8 and 12 = 4


References :

Data Structures and Algorithm Analysis in Java (3rd Edition)

Wikipedia = Greatest Common Divisor

Maximum Contiguous Subsequence Sum in Quadratic Time in Java

Finding the maximum contiguous subsequence sum of an array of integers among other subsequences is one of the basic problems about operations on arrays, indices and complexity analysis.

For the array {-2, -3, 4, -1, -2, 1, 5, -3}   the maximum subsequence sum contains elements
"4, -1, -2, 1, 5" so the sum = 4+(-1)+(-2)+1+5 = 7.

Using two for loops gives the solution so it is a quadratic O(n²) solution to maximum contiguous subsequence sum in quadratic time in Java.

Removing one of the extra for loops also helps to get rid of expensive operations so the quadratic time becomes preferable to cubic time solution.

package basics;

public class MaxSubSumQuadratic {

 public static int maxSubSum(int[] inArr) {

  int maxSum = 0;

  for (int i = 0; i < inArr.length; i++) {
   
   int thisSum = 0;
   
   for (int j = i; j < inArr.length; j++) {
   
    thisSum += inArr[j];

    if (thisSum > maxSum)
     maxSum = thisSum;
    
   }   
  }

  return maxSum;
 }

 public static void main(String[] args) {

  int input[] = { -2, -3, 4, -1, -2, 1, 5, -3 };

  System.out.println("Max Sub Sum Result = " + maxSubSum(input));

  input = new int[] { -2, 3, -16, 100, -4, 5 };

  System.out.println("Max Sub Sum Result = " + maxSubSum(input));

  input = new int[] { -2, 11, -4, 13, -5, 2 };

  System.out.println("Max Sub Sum Result = " + maxSubSum(input));

  input = new int[] { -15, -23, -476, -3, -292 };

  System.out.println("Max Sub Sum Result = " + maxSubSum(input));
 }

}

Create a MaxSubSumQuadratic.java file in your workspace.

When the main method inside the MaxSubSumQuadratic class executed it is going to print :

Max Sub Sum Result = 7
Max Sub Sum Result = 101
Max Sub Sum Result = 20
Max Sub Sum Result = 0



References :

Data Structures and Algorithm Analysis in Java (3rd Edition)

Maximum Contiguous Subsequence Sum in Linear Time in Java

Finding the maximum contiguous subsequence sum of an array of integers among other subsequences is one of the basic problems about operations on arrays, indices and complexity analysis.

For the array {-2, -3, 4, -1, -2, 1, 5, -3}   the maximum subsequence sum contains elements
"4, -1, -2, 1, 5" so the sum = 4+(-1)+(-2)+1+5 = 7.

Using one for loop gives the solution so it is a linear O(n) solution to maximum contiguous subsequence sum in linear time in java.

In this solution inside the for loop, if the currently added item leads to a larger result then the previous maximum then this becomes the new maximum.

If the newly added item leads to a negative sum result then the current sum is assigned the "0".

This solution works for the arrays that contain at least one positive integer.

package basics;

public class MaxSubSumLinear {

 public static int maxSubSum(int[] inArr) 
 {  
  int maxSum = 0, currentSum = 0;

  for (int j = 0; j < inArr.length; j++) {
   currentSum += inArr[j];

   if ( currentSum > maxSum)
    maxSum = currentSum;
   else if ( currentSum < 0)
    currentSum = 0;
  }

  return maxSum;
 }

 public static void main(String[] args) {

  int input[] = { -2, -3, 4, -1, -2, 1, 5, -3 };

  System.out.println("Max Sub Sum Result = " + maxSubSum(input));

  input = new int[] { -2, 3, -16, 100, -4, 5 };

  System.out.println("Max Sub Sum Result = " + maxSubSum(input));

  input = new int[] { -2, 11, -4, 13, -5, 2 };

  System.out.println("Max Sub Sum Result = " + maxSubSum(input));

  input = new int[] { -15, -23, -476, -3, -292 };

  System.out.println("Max Sub Sum Result = " + maxSubSum(input));
 }

}

Create a MaxSubSumLinear.java file in your workspace.

When the main method inside the MaxSubSumLinear class executed it is going to print :

Max Sub Sum Result = 7
Max Sub Sum Result = 101
Max Sub Sum Result = 20
Max Sub Sum Result = 0

References :

Data Structures and Algorithm Analysis in Java (3rd Edition)

Maximum Contiguous Subsequence Sum in Cubic Time in Java

Finding the maximum contiguous subsequence sum of an array of integers among other subsequences is one of the basic problems about operations on arrays, indices and complexity analysis.

For the array {-2, -3, 4, -1, -2, 1, 5, -3}   the maximum subsequence sum contains elements
"4, -1, -2, 1, 5" so the sum = 4+(-1)+(-2)+1+5 = 7.

Three different indexes defined to solve this problem which are i,j and k respectively.

Because of there are 3 for loops used to solve its time complexity is O(n³).

This solution works for the arrays that contain at least one positive integer.

package basics;

public class MaxSubSumCubic {

 public static int maxSubSum( int[] inArr )
 {
  int maxSum = 0;
  
  for (int i = 0; i < inArr.length; i++) {
   for( int j=i; j<inArr.length; j++ )
   {
    int currentSum = 0;
    
    for( int k=i; k<= j; k++ )
     currentSum += inArr[k];
    
    if( currentSum > maxSum )
     maxSum = currentSum;
   }
  }
  
  return maxSum;
 }
 
 public static void main(String[] args) {
  
  int input[] = {-2, -3, 4, -1, -2, 1, 5, -3};
  
  System.out.println("Max Sub Sum Result = "+maxSubSum(input));
  
  input = new int[]{ -2, 3, -16, 100, -4, 5 };
  
  System.out.println("Max Sub Sum Result = "+maxSubSum(input));
  
  input = new int[]{ -2, 11, -4, 13, -5, 2 };
  
  System.out.println("Max Sub Sum Result = "+maxSubSum(input));
  
  input = new int[]{ -15, -23, -476, -3, -292};
  
  System.out.println("Max Sub Sum Result = "+maxSubSum(input));
 }
}

Create a MaxSubSumCubic.java file in your workspace.

When the main method inside the MaxSubSumCubic class executed it is going to print :

Max Sub Sum Result = 7
Max Sub Sum Result = 101
Max Sub Sum Result = 20
Max Sub Sum Result = 0

References :

Data Structures and Algorithm Analysis in Java (3rd Edition)

Print Digits of A Number in Forward Or Backward Order in Java

Printing the separate digits of a number is another common example of using modulo operator.

Forward order display of separate digits of a number can be achieved with a recursive method and backward order display of separate digits of a number can be achieved with an iterative method in Java.

package basics;

public class PrintDigits {

 public static void printDigitsOfNumberInForwardOrder( int number )
 {
      if( number/10 > 0 )
          printDigitsOfNumberInForwardOrder(number/10);
  
      System.out.print(number%10+" ");
 }
 
 public static void printDigitsOfNumberInReverseOrder( int number )
 {
      while ( number > 0) {
          System.out.print(number%10+" ");
          number /= 10;
      }  
 }
 
 public static void main(String[] args) {
  
      int number = 1234;
      System.out.print("Digits of "+number+" in forward order are = ");
      printDigitsOfNumberInForwardOrder(number);
  
      number = 123429345;
      System.out.print("\nDigits of "+number+" in forward order are = ");
      printDigitsOfNumberInForwardOrder(number);
  
      number = 678123478;
      System.out.print("\nDigits of "+number+" in forward order are = ");
      printDigitsOfNumberInForwardOrder(number);
  
      number = 678123478;
      System.out.print("\nDigits of "+number+" in backward order are = ");
      printDigitsOfNumberInReverseOrder(number);
 }
}

Create a PrintDigits.java file in your workspace.

When the main method inside the PrintDigits class executed it is going to print :

Digits of 1234 in forward order are = 1 2 3 4
Digits of 123429345 in forward order are = 1 2 3 4 2 9 3 4 5
Digits of 678123478 in forward order are = 6 7 8 1 2 3 4 7 8
Digits of 678123478 in backward order are = 8 7 4 3 2 1 8 7 6

Static Generic Recursive Binary Search Algorithm In Java

Binary Search algorithm can be implemented recursively in a generic way in Java.

Generic recursive binary search method accepts input parameters as any item that implements Comparable interface.

Static binary search method was tested with Integer, Double and String type of parameters where each of them individually implements Comparable interface.

package basics;

import java.util.Arrays;

public class GenericRecursiveBinarySearch {

  public static <T extends Comparable<T>> int index( T[] items, T item )
  {
      return index( items, item, 0, items.length-1 );
  }
  
  public static <T extends Comparable<T>> int index( T[] items, T key, int low, int high )
  {
      if ( key == null )
          return -1;
   
      if( low > high  )
          return -1;
    
      int mid = low+(high-low)/2;
    
      if( key.compareTo( items[mid] ) > 0 )
          return index(items, key, mid+1, high);
      else if( key.compareTo( items[mid] ) < 0 )
          return index( items, key, low, mid-1 );
      else
          return mid;
  }  

  public static void main(String[] args) {

      Integer[] items = { 22, 55, 66, 11, 32, 56, 67, 89, 95, 10 };

      Arrays.sort(items);
      System.out.print("Sorted Integer Array = ");
      for (Integer item : items) {
           System.out.print(item+" ");
      }
  
      int foundIndex = index(items, Integer.valueOf(22));
      System.out.println("\nInteger Array Contains item 22 at index = " + foundIndex);

      foundIndex = index(items, Integer.valueOf(11));
      System.out.println("Integer Array Contains item 11 at index = " + foundIndex);

      foundIndex = index(items, Integer.valueOf(67));
      System.out.println("Integer Array Contains item 67 at index = " + foundIndex);

      foundIndex = index(items, Integer.valueOf(10));
      System.out.println("Integer Array Contains item 10 at index = " + foundIndex);

      foundIndex = index(items, Integer.valueOf(101));
      System.out.println("Integer Array Contains item 101 at index = " + foundIndex);

      foundIndex = index(items, null);
      System.out.println("Integer Array Contains item null at index = " + foundIndex);

      String[] strItems = { "alk", "abc", "adk", "zyt", "fre", "nhy" };
      Arrays.sort(strItems);

      System.out.print("\nSorted String Array = ");
      for (String item : strItems) {
           System.out.print(item+" ");
      }
  
      foundIndex = index(strItems, "alk");
      System.out.println("\nString Array Contains item alk at index = " + foundIndex);

      foundIndex = index(strItems, "nhy");
      System.out.println("String Array Contains item nhy at index = " + foundIndex);

      foundIndex = index(strItems, "zyt");
      System.out.println("String Array Contains item zyt at index = " + foundIndex);

      foundIndex = index(strItems, "zyts");
      System.out.println("String Array Contains item zyts at index = " + foundIndex);

      foundIndex = index(strItems, "null");
      System.out.println("String Array Contains item null at index = " + foundIndex);

      Double[] dItems = { 11.3, 13.3, 6.0, 9.6, 45.7, 23.2 };
      Arrays.sort(dItems);

      System.out.print("\nSorted Double Array = ");
      for (Double item : dItems) {
           System.out.print(item+" ");
      }
  
      foundIndex = index(dItems, 13.3);
      System.out.println("\nDouble Array Contains item 13.3 at index = " + foundIndex);

      foundIndex = index(dItems, 14.3);
      System.out.println("Double Array Contains item 14.3 at index = " + foundIndex);

      foundIndex = index(dItems, 23.0);
      System.out.println("Double Array Contains item 23.0 at index = " + foundIndex);

 }
}

Binary search works for sorted arrays so before calling binary search on arrays call Arrays.sort to sort array items.

Create a GenericRecursiveBinarySearch.java file in your workspace.

When the main method inside the GenericRecursiveBinarySearch class executed it is going to print :

Sorted Integer Array = 10 11 22 32 55 56 66 67 89 95
Integer Array Contains item 22 at index = 2
Integer Array Contains item 11 at index = 1
Integer Array Contains item 67 at index = 7
Integer Array Contains item 10 at index = 0
Integer Array Contains item 101 at index = -1
Integer Array Contains item null at index = -1

Sorted String Array = abc adk alk fre nhy zyt
String Array Contains item alk at index = 2
String Array Contains item nhy at index = 4
String Array Contains item zyt at index = 5
String Array Contains item zyts at index = -1
String Array Contains item null at index = -1

Sorted Double Array = 6.0 9.6 11.3 13.3 23.2 45.7
Double Array Contains item 13.3 at index = 3
Double Array Contains item 14.3 at index = -1
Double Array Contains item 23.0 at index = -1

Static Generic Iterative Binary Search Algorithm In Java

In order take advantage of Generics in Java, binary search method can be implemented generically.

Binary search works for sorted Arrays so Arrays.sort method is used before using binarySearch method.

Any type that implements Comparable interface is accepted by the generic iterative search method.

Built-in String, Integer and Double classes in Java implement Comparable interface so search method accepts these parameters.

package basics;

import java.util.Arrays;

public class GenericIterativeBinarySearch {

 public static <T extends Comparable<T>> boolean search( T[] items, T item ) {

  if (item == null) {
   return false;
  }

  int low = 0;
  int high = items.length - 1;

  while (low <= high) {

   int ix = low + (high - low) / 2;

   if (item.compareTo(items[ix]) < 0) {
    high = ix - 1;
   } else if (item.compareTo(items[ix]) > 0) {
    low = ix + 1;
   } else {
    return true;
   }
  }

  return false;
 }


 public static void main(String[] args) {

  Integer[] items = { 22, 55, 66, 11, 32, 56, 67, 89, 95, 10 };

  Arrays.sort(items);

  boolean found = search(items, Integer.valueOf(22) );
  System.out.println("Integer Array Contains item 22 = "+found);

  found = search(items, Integer.valueOf(11) );
  System.out.println("Integer Array Contains item 11 = "+found);

  found = search(items, Integer.valueOf(67) );
  System.out.println("Integer Array Contains item 67 = "+found);

  found = search(items, Integer.valueOf(10) );
  System.out.println("Integer Array Contains item 10 = "+found);

  found = search(items, Integer.valueOf(101) );
  System.out.println("Integer Array Contains item 101 = "+found);  
  
  found = search(items, null );
  System.out.println("Integer Array Contains item null = "+found); 
  
  String[] strItems = { "alk", "abc", "adk", "zyt", "fre", "nhy" };
  Arrays.sort(strItems);
  
  found = search( strItems, "alk" );
  System.out.println("String Array Contains item alk = "+found);
  
  found = search( strItems, "nhy" );
  System.out.println("String Array Contains item nhy = "+found);
  
  found = search( strItems, "zyt" );
  System.out.println("String Array Contains item zyt = "+found);
  
  found = search( strItems, "zyts" );
  System.out.println("String Array Contains item zyts = "+found);
  
  found = search( strItems, "null" );
  System.out.println("String Array Contains item null = "+found);
  
  Double[] dItems = { 11.3, 13.3, 6.0, 9.6, 45.7, 23.2 };
  Arrays.sort(dItems);
  
  found = search( dItems, 13.3 );
  System.out.println("Double Array Contains item 13.3 = "+found);
  
  found = search( dItems, 14.3 );
  System.out.println("Double Array Contains item 14.3 = "+found);
  
  found = search( dItems, 23.0 );
  System.out.println("Double Array Contains item 23.0 = "+found);  
  
 }
}

Create a GenericIterativeBinarySearch.java file in your workspace.

When the main method inside the GenericIterativeBinarySearch class executed it is going to print :

Integer Array Contains item 22 = true
Integer Array Contains item 11 = true
Integer Array Contains item 67 = true
Integer Array Contains item 10 = true
Integer Array Contains item 101 = false
Integer Array Contains item null = false
String Array Contains item alk = true
String Array Contains item nhy = true
String Array Contains item zyt = true
String Array Contains item zyts = false
String Array Contains item null = false
Double Array Contains item 13.3 = true
Double Array Contains item 14.3 = false
Double Array Contains item 23.0 = false

Find Permutations of a String Recursively in Java

In order to print all the permutations of a String a recursive method can be implemented.

In this recursive String permutation solution a StringBuilder instance is used as compared to other common String permutation implementations in Java.

package basics;

public class StringUtils {

 public static void permute( String str ) {
  print("", str);
 }

 private static void print(String leftPart, String str ) {

  int sLength = str.length();
  if ( sLength == 0) {
   return;
  } else if ( sLength == 1) {
   System.out.println(leftPart + str);
   return;
  }

  StringBuilder buffer = new StringBuilder(str);

  for (int i = 0; i < sLength; i++) {
   char temp = buffer.charAt(i);
   buffer.setCharAt(i, buffer.charAt(0));
   buffer.setCharAt( 0, temp );
   print( leftPart + temp, buffer.substring(1, sLength) );
  }
  
 }
 
 public static void main(String[] args) {
  
  String val = "abc"; 
  System.out.println("All Permutations of "+val);
  permute(val);  
  val = "abcd";
  System.out.println("All Permutations of "+val);
  permute(val);
  
 }

}

Create a StringUtils.java file in your workspace.

When the main method inside the StringUtils class executed it is going to print :

All Permutations of abc
abc
acb
bac
bca
cab
cba
All Permutations of abcd
abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
bdac
bdca
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba

Palindrome String Check Recursively in Java

Palindrome String checking is one of the primitive exercises for String processing char-by-char.

Palindrome String check can also be implemented recursively in Java. This recursive implementation is not efficient as the iterative one because it calls String.substring() subsequently.

package basics;

public class StringUtils {

 public static boolean isPalindrome( String str )
 {
  int sLength = str.length();
  if ( sLength < 2) {
   return true;
  } else if ( str.charAt(0) != str.charAt( sLength-1 ) ) {
   return false; 
  } else if ( sLength == 2 ) {
   return true;
  } else { 
   return isPalindrome( str.substring( 1, sLength-1 ));
  }
  
 }
 
 public static void main(String[] args) {
  
  String str = "madam";
  boolean result = isPalindrome(str);
  System.out.println(str+" is Palindrome = "+result);
  
  str = "qqaacc";
  result = isPalindrome(str);
  System.out.println(str+" is Palindrome = "+result);
  
  str = "cocoococ";
  result = isPalindrome(str);
  System.out.println(str+" is Palindrome = "+result);
 }
}

Create a StringUtils.java file in your workspace.

When the main method inside the StringUtils class executed it is going to print :

madam is Palindrome = true
qqaacc is Palindrome = false
cocoococ is Palindrome = true

Find Max Integer From The First N Integers of Unsorted Array Recursively in Java

Searching a sorted integer array for a specific integer is a general use-case for most of the time.

But if it is required to search an unsorted array for the first N elements in order to find the maximum element then it is required to apply a different solution.

In order to find the maximum of first N elements of an unsorted array recursively following method can be used.

package basics;

public class NumberUtils {

 public static int getMaxItemFromSubArray( int[] inArray, int index ) {
  
  if( index <= 0 || index>inArray.length )
   return -1;
  
  if ( index == 1 ) {
   return inArray[0]; 
  }
  
  int m = getMaxItemFromSubArray( inArray, index-1 ); 
  
  if ( inArray[ index-1 ] > m) {
   return inArray[ index-1 ];
  } else {
   return m;
  }
  
 }

 public static void main(String[] args) {

  int[] items = { 0, 5, 73, 33, 201, 3, 441 };
  int maxItem = getMaxItemFromSubArray( items , 0 );
  System.out.println("Max Item is = " + maxItem);  
  
  maxItem = getMaxItemFromSubArray( items , 8 );
  System.out.println("Max Item is = " + maxItem);  
  
  maxItem = getMaxItemFromSubArray( items , 3 );
  System.out.println("Max Item is = " + maxItem);  
  
  maxItem = getMaxItemFromSubArray( items , 4 );
  System.out.println("Max Item is = " + maxItem); 
  
  maxItem = getMaxItemFromSubArray( items , 5 );
  System.out.println("Max Item is = " + maxItem); 
  
  maxItem = getMaxItemFromSubArray( items , 6 );
  System.out.println("Max Item is = " + maxItem); 
  
  maxItem = getMaxItemFromSubArray( items , 7 );
  System.out.println("Max Item is = " + maxItem); 
  
 }
}

Create a NumberUtils.java file in your workspace.

When the main method inside the NumberUtils class executed it is going to print :

Max Item is = -1
Max Item is = -1
Max Item is = 73
Max Item is = 73
Max Item is = 201
Max Item is = 201
Max Item is = 441

Sum of the Squares of the First n Numbers Recursively in Java

Formula for the sum of the squares of the first n numbers is described with the following equation in mathematics.

 f(n) = [n(n+1)(2n+1)]/6

In order to get the result for the sum of the first n integers in Java a recursive method can be used.

package basics;

public class NumberUtils {

 public static int sumOfFirstNSquares( int number )
 {
  if( number == 0 )
   return 0;
  
  return sumOfFirstNSquares(number-1)+(number*number);
 }
 
 public static void main(String[] args) {
  
  int sum = sumOfFirstNSquares(5);
  System.out.println("Sum is = "+sum);
  
  sum = sumOfFirstNSquares(7);
  System.out.println("Sum is = "+sum);
  
  sum = sumOfFirstNSquares(11);
  System.out.println("Sum is = "+sum);
 }
}

Create a NumberUtils.java file in your workspace.

If you are willing to work with real big numbers in Java then a BigInteger can be a solution.

When the main method inside the NumberUtils class executed it is going to print :

Sum is = 55
Sum is = 140
Sum is = 506

Print Singly Linked List in Reverse Order Recursively in Java

Arrays have got constant size restriction when they are created so it is expensive to resize them dynamically in an application. Instead of using arrays for resizing dynamic structure requirements, singly linked list data structure can be used.

Singly linked list has got a node based structure where each node has got next and data fields.

Above is a singly linked list with 1-2-3-4-5 elements.

In order to print data elements of each node of a singly linked list data structure in Java following forwardPrint and reversePrint methods can be used.

reversePrint is a recursive method and assumes that the head node is not null.

package basics;

public class LinkedList {

 static class Node
 {
  Node next;
  int data;
 }

 private Node head;
 
 public LinkedList(Node pHead) {
  head = pHead; 
 } 
 
 public void forwardPrint()
 {
  forwardPrint(head);
 }
 
 private void forwardPrint( Node node )
 { 
  Node current = head;
  while( current!=null )
  {
   System.out.println(current.data);
   current = current.next;
  }
 }
 
 public void reversePrint()
 {
  reversePrint(head);
 }
 
 private void reversePrint( Node node )
 {
  if( node.next != null )
   reversePrint(node.next);
  
  System.out.println(node.data);
 }
 
 public static void main(String[] args) {
  
  Node node1 = new Node();
  node1.data = 1;
  Node node2 = new Node();
  node2.data = 2;
  Node node3 = new Node();
  node3.data = 3;
  Node node4 = new Node();
  node4.data = 4;
  Node node5 = new Node();
  node5.data = 5;
  node1.next = node2;
  node2.next = node3;
  node3.next = node4;
  node4.next = node5;
  node5.next = null;
  
  LinkedList list = new LinkedList(node1);
  System.out.println("Forward Print Linked List = ");
  list.forwardPrint();
  System.out.println("Backward Print Linked List = ");
  list.reversePrint();
 }
}

Node objects are created separately and node1 object sent as the head of the linked list. Create a LinkedList.java file in your workspace.

When the main method inside the LinkedList class executed it is going to print :

Forward Print Linked List =
1
2
3
4
5
Backward Print Linked List =
5
4
3
2
1