Topics: Recursion and Merge-sort Problem Description Please make sure to read the document fully before starting! In this assignment, you will be tasked with writing methods that will solve some puzzles recursively. For some of them, you will need to use the merge method from Recursion Utils.java, which will be provided. NOTE: you can ignore any Checkstyle errors in Recursion Utils.java and Point.java since they are provided code files. Solution Description For this assignment, you will create the following class: Recursion.java Notes: 1. You will be able to use provided helper methods from Recursion Utils.java and Point.java. Review the Javadoc for those methods. 2. The methods in this assignment should be public and static, as they are procedures that do not use any instance data. 3. All methods in this assignment must use recursion or call recursive helper methods. a. INDICATE WHICH METHODS ARE RECURSIVE IN YOUR COMMENTS 4. Make sure to add all Javadoc comments to your methods Recursion.java This class will hold all the recursive methods you will be implementing. Methods: mergeSort Takes in a String[] and returns a String[] containing the elements of the input sorted in ascending lexicographical order. O O O O The input array will not be null or contain null entries. This algorithm must sort the input array using merge sort, as taught in lecture. When merging two arrays, you must use the merge method from Recursion Utils.java. Example 1: Input: ["Brian", "Alex", "David", "Charlie", "Aaron"] Output: ["Aaron", "Alex", "Brian", "Charlie", "David"] HINT: You may the copyOfRange method helpful in RecursionUtils.java mergeAll Takes in a String[] [], where each index stores an ascending sorted array of Strings. O O O The input array will not be null or contain null entries. Returns a String[] containing all Strings from each index of the input in ascending lexicographical order. When merging two arrays, you must use the merge method from RecursionUtils.java. This method must be recursive or call recursive helper methods. Example: Input: [["Alex", "Brian"], ["Aaron", "David"], ["Charlie"]] Output: ["Aaron", "Alex", "Brian", "Charlie", "David"] count Duplicates Takes in a String[], which will be sorted in ascending lexicographical order. Returns an int, representing the number of duplicate elements in the input array. This method must be recursive, meaning that it will call itself at some point. Example: Input: ["A", "A", "B", "C", "C", "C", "D"] Output: 3 Reason: "A" is duplicated once, and "C" is duplicated twice. All other elements are unique. Thus, there are a total of three duplicates in the input. verify Palindrome Takes in a String. Returns a boolean, representing if the input string was a palindrome. If the input is an empty string, return true. o If the input is null, return false. A palindrome is a String that reads the same forwards and backwards Ex: The word "racecar" read backwards is still "racecar". Therefore, racecar is a palindrome. This method must be recursive, meaning it will call itself at some point This method should check if the String is palindrome regardless of casing (i.e. it should be case-insensitive). Example: Input: Civic Output: true, "Civic" backwards is "civic" Example: Input: "java" Output: false, "java" backwards is "avaj" Example: Input: "tacocat" Output: true, "tacocat" backwards is "tacocat" numInteriorPoints o Takes in a Point[] and an int. 0 0 The first parameter (Point[]) represents the Cartesian coordinates for a set of points. Each index stores a Point, representing the coordinate pair of a point. The x field represents the x-coordinate. The y field represents the y-coordinate. The second parameter (int) represents the radius of a circle centered at the origin. Return an int representing the number of points that are strictly within the circle. HINT: Think about how you can use the Pythagorean Theorem in this situation This method must be recursive or use recursive helper methods. o Example: Input: [(1, 1) (0, 0) (3, 4) (5, 5)], 5 Output: 2, the first two points are within the circle of radius 5. The last two points have distance of 5 or more from the origin, and thus are not inside of the circle Allowed Imports To prevent trivialization of the assignment, you are not allowed to use any imports. Submission To submit, upload the files listed below to the corresponding assignment on Gradescope: Recursion.java