Objectives Analyze a problem that can be solved with recursion Develop a recursive algorithm Write a static recursive method Description You will be solving two simple problems using recursion. These may be easy enough that you can get by without thinking too much about how recursion affects the design, but the practice will be helpful for when you tackle more complex recursive problems. Recursion is a difficult topic to fully understand (possibly the hardest topic you'll learn in this class), and it will come up in many of the algorithms and data structures you learn about for the rest of the semester. To make sure you are using recursion rather than a shortcut method or a loop, the following words are not allowed in your code (a test case will check that they do not exist): for while import replace Design Completing the written work below is optional, but it may help you better understand the design of your algorithms before coding them. Part 1 - Outline 1. Break the problem into two parts: a smaller version of the problem you're attempting to solve, and a trivial problem that can be solved with no recursion. 2. Restate the problem in terms of the smaller recursive problem and the trivial problem from step 1. 3. What is the base case for this problem? This would be a set of input or a scenario where you only need to solve the trivial problem, or you don't need to do anything. The smaller recursive problem should not need to be solved in order for you to solve the base case. 4. In order for this algorithm to be practical, we need to guarantee that we always reach our base case. How do you know that the base case will always be reached? Do you need to make any assumptions about the input to guarantee this? Part 2 - Algorithm Steps . . Your answers to the questions in part 1 should give you most of what you need to devise a recursive algorithm that solves the problem. Start with a list of input for your algorithm. State the name, type, and purpose of each input value. Write step by step instructions for solving the problem. If a step involves calculating a new value, make sure you provide a name for that value so that it can be referred to in later steps. These instructions should be in English/pseudocode. NOT code. Your input and instructions should be consistent with your answers to the questions in part 1. If you can't write directions consistent with those answers, you may need to go back and revise the answers. The algorithm must be recursive. If you don't have a step that performs the entire algorithm again (with different input), then your algorithm isn't recursive. . Problems Code a recursive algorithm for each of the problems below. Each recursive algorithm should be a static method in the class Recursion. Use the method name and parameters given after the problem. Problem #1: fillArray(arr: int[], n:int) NOTE: This method has no return value because it mutates the input array. You can have it return the array if you want to, but this isn't necessary. Starting at an Index N, fill an array of integers so that each value is equal to its index plus 1 (in other words, for any valid index i all should equali+1). Here are a few examples: Input: Array = {0,0,0,0); N=0 Output: Array = {1,2,3,4) Input: Array = {0,0,0,0); N = 2 Output: Array = {0,0,3,4) Input: Array = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1); N = 0 Output: Array = {1,2,3,4,5,6,7,8,9,10) Input: Array = {10, 9, 8, 7, 6,5,4,3,2,1); N = 4 Output: Array = {10, 9, 8, 7, 5, 6, 7, 8, 9, 10) Problem #2: repChar(str: String, x: char, y: char): String Replace each character X in a string with a different character Y. Note that X and Y aren't the literal characters we're replacing, they're just variables. They can each be any character, and must be included in your input. Here are some examples: Input: String = "HELLO WORLD"; X = "L; Y = '0' Output: "HEOOO WOROD Input: String = "HELLO WORLD"; X = '0; Y = 'E' Output: "HELLE WERLD Input: String = "HELLO WORLD"; X = 'A'; Y = 'E Output: "HELLO WORLD