Question

Lab #3 – Recursion on Strings Lab Objectives • Be able to write a recursive Java method for Java strings • Be able to make use of exploit natural conversion between strings and integers • Be able to write a driver to call the methods developed for testing Deliverables Submit the report in Word or PDF format with the results of every task listed below. They should show screen capture of your results. The problem String as a sequence of characters for developing recursive method Given a Java string object, we observe that it is a sequence (or ordered list) of characters. Our goal is to employ a very common technique in computer science—namely, dividing the list into its head (it’s first element) and its tail (the remaining list with the first element removed). We can then recurse on the tail, which happens to be smaller. We use this technique for reversing a string, or for checking whether it is a palindrome (reads the same if you read it from left or right). Task #1 Develop a left recursive method to reverse a string Develop a method with the prototype public static String reverseRecursiveLeft (String input) based on selecting the leftmost character as the head and the remaining part of the string as its tail. Here is the recursive design. 1. Base case: The problem is trivial when the string length is 0 or 1. 2. Decomposition: For strings of length > 1: • Extract its head (character) and the tail. You are expected to know the string methods needed to achieve this. • Make a recursive call to obtain the tail reversed. 3. Composition: Append (concatenate) the head to obtain the original string reversed. Task #2 Develop a right recursive method to reverse a string Develop a method with the prototype public static String reverseRecursiveRight (String input) based on selecting the rightmost character as the head and the remaining part of the string on its left as the tail. The only difference in the recursive design is that the reversed tail needs to be appended after the head character. Page 2 of 2 Task #3 Develop a middle recursive method to reverse a string Develop a method with the prototype public static String reverseRecursiveMiddle (String input) This time, instead of extracting one element (character) from left or right, extract two characters simultaneously from both left and right. design. This leads to a drop of 2 in size of the reduced problem. Be careful to take this into account when you design the base case. Should the base case be any different? Consider odd and even size strings Task #4 Develop a method to reverse an integer (as written in decimal form) Develop a method with the prototype public static int reverse (int input) using any of the previous three methods you developed for reversing a string. Note that, • For a negative integer, the result should also be negative with the digits reversed, i.e., your method should return -321 when presented with input -123. • You can make use of the toString() method available to any object. However, wrapper classes are needed for this, while operating on a primitive variable such as int. • The reconversion is easily achieved by the parse family of methods also available in the wrapper class. Task #5 Develop a middle recursive method to check whether a string is palindrome. Develop a method with the prototype public static boolean isPalindrome (String input) to check if a string is a palindrome. Determine which of the three types of recursion (left, right, or middle) maps directly to this problem. Also, overload the isPalindrome() for integer inputs as public static boolean isPalindrome (int input) using the same technique of integer-string inter-conversion. The same rule of reversing applies to negative numbers, i.e., only digits are considered for deciding whether the number is a palindrome. Write a driver to test your program and include screen captures in your report.

Answer 1

public class Main {
  
   // methods to implement
   public static String reverseRecursiveLeft (String input) {
       // base case
       if(input.length() <= 1) {
           // if string have 1 or less character left return the string
           return input;
       }  
       // recursive solution
       // for string greater then 1 character long divide it in to head and tail part
       String head = input.substring(0, 1); // get first character from substring method
       String tail = input.substring(1); // get remaining character from substring method
       // make recursive call to obtain tail in reverse and append head to it
       return reverseRecursiveLeft(tail) + head;
   }

   public static String reverseRecursiveRight (String input) {
       // base case
       if(input.length() <= 1) {
           // if string have 1 or less character left return the string
           return input;
       }  
       // recursive solution
       // for string greater then 1 character long divide it in to head and tail part
       String head = input.substring(input.length()-1); // get the right most character from substring method
       String tail = input.substring(0,input.length()-1); // get remaining character from substring method
       // make recursive call to obtain tail in reverse and append it to head
       return head + reverseRecursiveLeft(tail);
   }
  
   public static String reverseRecursiveMiddle (String input) {
       // base case
       if(input.length() <= 1) {
           // if string have 1 or less character left return the string
           return input;
       }  
       else if(input.length()==2) {
           // if string have 2 character return them in reverse order
           String left = input.substring(0, 1);
           String right = input.substring(1, 2);
           return right + left;
       }
       // recursive solution
       // for string greater then 2 character long divide it in to head, middle and tail part
       String head = input.substring(0, 1); // get the left most character from substring method
       String tail = input.substring(input.length()-1); // get the right most character from substring method
       String middle = input.substring(1,input.length()-1); // get remaining character from substring method
       // make recursive call to obtain middle in reverse and append it to tail then append the head
       return tail + reverseRecursiveLeft(middle) + head;
   }
  
   public static int reverse (int input) {
       // check if input is negative
       if(input < 0) {
           // turn input in to positive integer as only digits are reversed
           input = input * -1;
           // convert integer to string with wrapper class
           String str = Integer.toString(input);
           // reverse the string
           String reverseDigit = reverseRecursiveLeft(str);
           // convert string to integer
           int integer = Integer.parseInt(reverseDigit);
           // return the integer with negative value
           return integer*-1;
       }
       else {
           // convert integer to string with wrapper class
           String str = Integer.toString(input);
           // reverse the string
           String reverseDigit = reverseRecursiveLeft(str);
           // convert string to integer
           int integer = Integer.parseInt(reverseDigit);
           // return the integer
           return integer;
       }
   }
  
   static boolean isPalindrome (String input) {
       // base case
       if(input.length() <= 1) {
           // if string have 1 or less character left return true as the character is in middle of the string
           return true;
       }  
       else if(input.length()==2) {
           // if string have 2 character check are they equals
           String left = input.substring(0, 1);
           String right = input.substring(1, 2);
           return left.equals(right);
       }
       // recursive solution
       // for string greater then 2 character long divide it in to head, middle and tail part
       String head = input.substring(0, 1); // get the left most character from substring method
       String tail = input.substring(input.length()-1); // get the right most character from substring method
       String middle = input.substring(1,input.length()-1); // get remaining character from substring method
       // make recursive call to check if middle is palindrome
       // compare head and tail and return the result with logic and with middle
       return head.equals(tail) && isPalindrome(middle);
   }
  
   public static boolean isPalindrome (int input) {
       // check if input is negative
       if(input < 0) {
           // turn input in to positive integer as only digits are counted for palindrome
           input = input * -1;
       }
       // convert integer to string
       String str = Integer.toString(input);
       // return if string is in palindrome
       return isPalindrome(str);
   }
  
   // main method to run program
   public static void main(String args[]) {
       String str = "hello world!";
       System.out.println("Reverse of ");
       System.out.println(str);
       System.out.println("by reverseRecursiveLeft is:");
       System.out.println(reverseRecursiveLeft(str));
       System.out.println("by reverseRecursiveRight is:");
       System.out.println(reverseRecursiveRight(str));
       System.out.println("by reverseRecursiveMidlle is:");
       System.out.println(reverseRecursiveMiddle(str));
       System.out.println();
      
       int p = 423651;
       System.out.print("Reverse of ");
       System.out.print(p);
       System.out.print(" is: ");
       System.out.println(reverse(p));
       System.out.println();
      
       int n = -54637;
       System.out.print("Reverse of ");
       System.out.print(n);
       System.out.print(" is: ");
       System.out.println(reverse(n));
       System.out.println();
      
       String s = "AbcDcbA";
       System.out.print(s);
       System.out.print(" is palindrome? ");
       System.out.println(isPalindrome(s));
       System.out.println();
      
       System.out.print(n);
       System.out.print(" is palindrome? ");
       System.out.println(isPalindrome(n));
       int pali = 1258521;
       System.out.print(pali);
       System.out.print(" is palindrome? ");
       System.out.println(isPalindrome(pali));
   }
}