Recursion java assignment

Recursion java assignment
Recursion Lab CSC 385 Description The following lab consists of problems that must be solved using recursion. Remember, recursion is when a method calls itself either directly or indirectly. For most, recursion is a tough not because the basics are difficult but turning a problem into one that can be solved recursively is difficult. Recursion isn’t just an interesting way to write a loop but a way of thinking and problem solving and with practice you, too, can master recursive thinking. For each of these problems, we will discuss the general idea, inputs and expected outputs, and the algorithm. It will be your job to implement the algorithm in Java. You will be given a RecursionLab.java file. Once you’ve implemented the solution to the problems submit a zip with the Java file that contains your implementations and this document which contains your worked problems. There are 5 problems in total. R01: Reverse a string Write a recursive method that accepts a string and returns a version that is reversed. You may assume the input is never null. Example Input Expected Output “Hello world.” “.dlrow olleH” “This is a string” “gnirts a si sihT” “” “” “abcdcba” “abcdcba” First, the simplest version of this problem is a string that is either empty or has 1 character. This will become our base case. If string has a length of 1 or less return the string. Now, for the reconstructing of the string. We want to reduce the problem toward the base case. That is we take a character out of the string for each successive call. For instance, lets look at the string “abc” reverseString – abcreverseString – bcreverseString – c Here, we’ve removed the first character for each successive call of reverseString and reduced the string down to 1 character. Now we need to build back up to get a reversed string. This will largely depend on where we make the recursive call. Suppose we do string.charAt(0) + reverseString(restOfString). This will not work because we are taking the first character of the string and concatenating it to the rest of the string. What we want is to take the rest of the reversed string and concatenate it to the first character of the string. So, rephrasing the problem as a recursive solution we say the following: Take the reversed string and concatenate first character to the end of it. This gives us the rest of our pseudocode. String reverseString(string) { if(string has length less than or equal to 1) { return string; } reversed = reverseString(rest of string) + first character of string return reversed; Provide a trace of calling reverseString(“abc”) below. R02: Sum Digits Compute the sum of the digits of a number. Note that % 10 will give the rightmost digit and / 10 will remove the rightmost digit. Assume the number will be >= 0. Example Input Expected Output 123 3919 22 17 First, let us consider the base case. This might not seem obvious at first, but the description gives a hint as to what we need to do. First, we need to reduce the problem down somehow. Removing a digit sounds like a reduction of some kind so let’s see what happens if we remove the rightmost digit. (Note, this is integer division. Decimals have no place here). 123 / 10 = 12 12 / 10 = 1 1 / 10 = 0 If we keep going, we will keep getting 0. So, reducing the number down to 0 looks like a base case. Every number will do this. So our base case becomes If the number is 0 return 0. The recursive case must take the rightmost digit and add it to the sum of the rest of the digits. To get the rightmost, again, look at the description. Here is an example 123 % 10 = 3 12 % 10 = 2 1 % 10 = 1 We take these two ideas and get the following pseudocode Int sumDigits(int num) { If(num is 0) { Return 0; } Return rightmost digit + sumDigits(rest of number) Perform a trace with num = 39312. R03: Sum positives only Write a recursive method that takes an array and returns the sum of only the positive integers. Example Input Expected Output [1, 2, 3] [-3, 4, -6, -10, 8] 12 [-3, -2, -1] [] For this one, we need to consider the arguments to the method. First, we will need the array but for each element we need an index to retrieve from the array. Let’s look at a purely iterative solution to see what this means. for(int idx = 0; idx < array.length; idx += 1) { if(array[idx] > 0) { sum += array[idx]; } This should already give you an idea of what the base case should be. In the above, we stop our iteration when our index variable, idx, is equal to or greater than the length of the array. That’s because once we’ve reached the end of the array, we’ve done the checks for each value. Our base case will become If our index variable is equal to or greater than the arrays length, we should return 0. Also, if the index is less than 0 we should return 0. Why return 0? Well, we need to return something according to the method header and 0 won’t affect the final result. Next is the recursive call. Actually, there will be 2 recursive calls. Look at the above loop again. There is an implicit assumption that if the number is less than or equal to 0 that we do nothing but we keep going. If we just stick to one recursive call we will not get every value. We need to actually perform a check and do two different calls. Lets think about this. If the number at array[idx] is positive then we need to add it to the final sum. If the number at array[idx] is not a positive value then we need to skip it and move on to the next number. This leaves us with the following If(array[idx] > 0) { Add the value at array[idx] to the sum of the rest of the positive integers, if there are any, in the array. } else { Skip this value and move on to the next number. You’ll find that the recursive calls are the exact same but we have to do an extra calculation for one of the lines. To “Add the value at array[idx] to sum of the rest of the positive integer” we just do that, array[idx] + recursive call. To skip the number and move on we simply do not do the addition and just make the recursive call. This gives us all the information needed to complete the pseudocode. Int sumPositives(int array[], int idx) { If(array[idx] is less than 0 or greater than array length) { Return 0; } If(array[idx] > 0) { Return array[idx] + sumPositives(rest of array); } else { Return sumPositives(rest of array); } Perform a trace with array = [1, -2, 3] and idx = 0. R04: 1D Maze You are given an array of length N and a jump size M. Each element of the array is either 0 or 1. A 0 indicates a location we can be at and a 1 indicates a location we cannot occupy. Hence, you can only move to a location in the array which contains a 0. You start at the 0th index which will always have a 0. For each move you can do one of the following Move one step forward Move one step backward Jump exactly M spaces forward. The new position must contain a 0. You may also move to any position N – 1 (outside the array). However, you may not move backward from position 0. If you can move to any position greater than N – 1 you have escaped the maze. Write a recursive method that returns true if you can escape otherwise return false. Example Input Expected Output [0, 1, 0, 0, 1] with jump = 2 true [0, 1, 1, 0, 1] with jump = 2 false [0, 1, 0, 0, 0, 1, 1, 0, 1] with jump = 2 false [0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1] with jump = 3 true This problem is different than the problems we’ve seen so far because it is not a linear problem. This is known as a decision problem and a backtracking problem. We need to decide for our current location, get a new location, and determine if that helps solve the problem. If it does not then we need to go back to a previous location and try a different decision. This sounds hard but this type of problem is perfect for recursion because the stack instances created by the recursive calls will hold our previous locations. Furthermore, for each call if one decision doesn’t work we can move on to the next one by simply make a different call. Before we get to the base cases lets explore what we are being asked to do with some of the examples. The order in which we perform the actions will be the same as the list above. If one decision fails then we move to the next for a given location. If we return to a position we continue with the next decision (we don’t restart). Lets look at an example run of the first input. [0, 1, 0, 0, 1], jump = 2 ^player We try to move forward but we can’t. We try to move backward but we can’t from position 0. We can jump 2. [0, 1, 0, 0, 1], jump = 2 ^ playerFrom our new position we can move forward [0, 1, 0, 0, 1], jump = 2 ^ playerFrom this position, we cannot move forward. We can move backward…. but if we do, we end up in a loop. (Try it) The key is that we need to keep track of where we’ve been, so we don’t do any more calculations on that spot. You can think of this like leaving cookie crumbs in an actual maze. Suppose we leave a 1 where we’ve been before making a move. [0, 1, 0, 0, 1], jump = 2 ^idx = 0 Place a 1 at our current location. Maze becomes [1, 1, 0, 0, 1]We can’t move forward.We can’t move backward from index 0.We can jump. [1, 1, 0, 0, 1], jump = 2 ^ idx = 2 Place a 1 at our current location. Maze becomes [1, 1, 1, 0, 1]We can move forward. [1, 1, 1, 0, 1], jump = 2 ^ idx = 3 Place a 1 at our current location. Maze becomes [1, 1, 1, 1, 1] We can’t move forward.We can’t move backward (because we’ve already been there)We can jump [1, 1, 1, 1, 1] ^ idx = 5 We passed N – 1 so we are out of the maze. This will return true. Try this with the rest of the mazes to convince yourself. Just note that if you go back to a previous location, while it has a 1 because you set a crumb there, you can still try the other choices. I have provided one more breakdown for the 3rd maze after the pseudocode. Now that we understand the problem and the details all that is needed is to determine the base case, or in this case, base cases and the recursive calls. If you read the description carefully, you can see we are given all of the base cases for this problem. If we make it out of the maze, we return true. If we move onto a location which is not allowed we return false. That’s pretty much it. Next, the recursive case is just the encoding of all of the decisions we need to make. The recursive case will be to either move forward 1 space, move backward 1 space, or to jump M spaces. How can we make these decisions? Well, we either increase or decrease the index by that much. For instance, isSolvableMaze(maze, idx + 1, jump) will move forward. The recursive cases should be setup up in a way to handle out of bounds issues such as trying to go backwards from the 0th position or moving out of the maze. All that is left is to combine these decisions and determine whether we can escape or not. Let me give you a sentence that should help with that. Either we move forward 1 space or we move backward 1 space or we jump M spaces. Is there any words in that sentence that gives you a hint as to how to combine the decisions? Remember that the recursive calls return a Boolean. If you thought that we should OR the return values of make the decisions then you would be correct. This makes not just logical sense but physical sense as you cannot move forward and backward at the same time as would be implied by a logical AND. So now we have enough to write the pseudocode. Boolean isSolvable1DMaze(maze, idx, jump) { If(we made it out) { Return true; } If(we are at a bad location) { Return false; } Place a bread crumb at our current location. Return move forward? || move backward? || jump?; 3rd Maze [0, 1, 0, 0, 0, 1, 1, 0, 1] with jump = 2 ^idx = 0Place a 1 at current location. Maze becomes [1, 1, 0, 0, 0, 1, 1, 0, 1] Can’t move forward.Can’t move backward from 0th position.Can Jump. [1, 1, 0, 0, 0, 1, 1, 0, 1] with jump = 2 ^ idx = 2 Place 1 at current location. Maze becomes [1, 1, 1, 0, 0, 1, 1, 0, 1] Can move forward. [1, 1, 1, 0, 0, 1, 1, 0, 1] with jump = 2 ^ idx = 3 Place 1 at current location. Maze becomes [1, 1, 1, 1, 0, 1, 1, 0, 1] Can move forward. [1, 1, 1, 1, 0, 1, 1, 0, 1] with jump = 2 ^ idx = 4 Place 1 at current location. Maze becomes [1, 1, 1, 1, 1, 1, 1, 0, 1] Can’t move forward.Can’t move backward.Can’t jump. We return to previous location. [1, 1, 1, 1, 1, 1, 1, 0, 1] with jump = 2 ^ idx = 3 Move forward failed.Can’t move backward.Can’t jump. We return to previous location. [1, 1, 1, 1, 1, 1, 1, 0, 1] with jump = 2 ^ idx = 2 Move forward failed.Can’t move backward.Can’t jump. We return to previous location. [1, 1, 1, 1, 1, 1, 1, 0, 1] with jump = 2 ^idx = 0 Jump failed and that was our last decision. We return false because we cannot escape this maze. No trace necessary for this problem. R05: Target to Sum Given an integer array and a target write a recursive method to determine if there exists a sublist of integers that sum to the target. Each number at a given index can only be used exactly once. Example input Expected output [2, 4, 8] target = 10 True (2 + 8 = 10) [2, 4, 8] target = 11 False (there is no sublist of integers that sums to 11) {1, -3, -8, 1, 6} target = 9 False (There is no sublist of integers that sums to 9) [-51, -99, 88, -89, 34, 63, -100, 77, 43, 12] target = 33 True (-51 + -99 + 88 + 63 + -100 + 77 + 43 + 12= 33) For this problem, I have given you the recursive solution in Java. It is the targetSum method. All you need to do is provide an explanation for how the recursive solution works. Explain the base case and recursive calls. private static boolean targetSum(int arr[], int idx, int sum, int target) { if(idx >= arr.length) { return sum == target; } return targetSum(arr, idx + 1, sum + arr[idx], target) || targetSum(arr, idx + 1, sum, target); A little background about this problem, it is like the 1D maze in that it is a backtracking decision problem. It is also a known NP-Complete problem. Provide algorithm explanation here.
Recursion java assignment
public class RecursionLab { public static void main(String args[]) { System.out.println(reverseString(“Hello world.”)); System.out.println(sumDigits(3919)); System.out.println(sumPositives(new int[] {9, 0, -3, 5, 7, -6}, 0)); System.out.println(solvable1DMaze(new int[] {0, 1, 1, 0, 0, 1, 0}, 0, 2)); System.out.println(targetSum(new int[] {-51, -99, 88, -89, 34, 63, -100, 77, 43, 12}, 0, 0, 33)); } private static String reverseString(String s) { return null; } private static int sumDigits(int num) { return 0; } private static int sumPositives(int arr[], int idx) { return 0; } private static boolean solvable1DMaze(int maze[], int idx, int jump) { return false; } private static boolean targetSum(int arr[], int idx, int sum, int target) { if(idx >= arr.length) { return sum == target; } return targetSum(arr, idx + 1, sum + arr[idx], target) || targetSum(arr, idx + 1, sum, target); }