CS 143 Assignment2 Recursive Fill, Swap, and Shuffle 25 at 1159 PM DUE on Thursday, J The methods specified below must be implemented recursively: no "while", "do while" or "for is allowed and no use of the Java Foundation Classes (work directly with the array of ints using basic Java operations). Also, no static variables. You will probably need to use the "recursive bootstrapping technique that we used with the find method in class and write additional method(s) to help you. Part 1(25 points): Implement a method fibFill which will fill (overwrite) an array with the Fibonacci sequence as defined in class. Element 0 should contain Fo element 1 F1-1, element 2 F;" Fe* F12, and so forth. public static void fibFill(int] a) The method will have the following signature Part 2 (50 points): Implement a method which will swap the first and second half of a portion of an array of ints. The method will have the following signature: public static void swapHalves(int a, int start, int length) Start indicates which index to start at and length the number of elements to include in the portion. You may assume the length is even. Example: int[] a = {19, 22, 31, 43, 54, 65, 78, 87} 31 10 Call to swapHalves(a, 0, 8) will modify a to look like the following 65 78 65 78 87 10 31 Part 2 Extra Credit (3 Points). If length is not even, move the first In/2] (n/2 rounding down) elements to the end and the last [n/21 (n/2 rounding up) elements to the front. Example: int[] a = {10, 22, 31, 43, 54, 65, 78, 87, 99) 10 Call to swapHalves(a, 0,9) will modify a to look like the following 31 43 65 78 65 78 87 31 Part 3 (25 points): Implement a swapShuffle routine which shuffles an array of ints. If the length is 1, do nothing. Otherwise, call swapHalves on the array, then recursively call swapShuffle on the first and second halves of the portion (consider each of those pieces to be like their own array). Return the number of times that swapHalves is called in total. You may assume the length is a power of two. public static int swapShuffle(int[] a) Example: [1, 2,3,4) will become 14,3, 2, 1) and return 3. (First, swapHalves sets up the array [3,4,1, 21 then recursively the first and second halves will each be swapped.) Part 3 Extra Credit (1 Point). Allow the length to be other than a power of two. Swap the two halves as they were swapped above. You have to implement Part 2 Extra Credit for this to count