Introduction
You have learned about recursion in previous lectures, and today, you will be practicing more skills to hone your ability to use recursion to solve a problem.
Remember when developing a recursive method, you must consider the base case and the recursive case.
- Base case: This is how your program knows to stop calling a method repeatedly. Consider, how do you know when the problem is solved, or you’re no longer able to perform the same function?
- Recursive case: This is where you call the same method you are currently executing in, with different parameters. How can you break the problem into smaller pieces that can be solved more easily?
For this assignment, you will be working with various methods to manipulate strings using recursion.
The method signatures are included in the starter code below, with a more detailed explanation of what function the method should perform.
You will be writing the following methods:
stringClean()palindromeChecker()reverseString()totalWord()permutation()
You will be using tools in the String class like .substring(), .charAt(), and .length() in all of these methods, so be careful with indices. If you get stuck, think about the base case of the method, then what needs to be done in the recursive case.
Do not use a loop in any of the methods except permutationHelper(). You may use a loop in permutationHelper() but there should be a recursive call in the method.
Include your own testing in main after instantiating an object of the class to check that your methods are working as expected.
For more recursion practice (or any other subject practice with Java), visit Coding Bat for some great problems to test your skills.
Step 1: reverseString()
Given a string, recursively reverse the letters to yield a new string. For example, if given “abcde”, the method would yield “edcba”.
When considering the base case and recursive case for this method, consider how we could convert an iterative way of doing the same function.
When reversing a string, we would start from the end of the string, and add the characters one by one to a new string so they are in opposite order.
How could we get the last character of the string repeatedly, and what new string would we pass into the method in its recursive call?
How would we know when to stop cutting off the last character and adding it to the new string?
Step 2: totalWord()
Given a string, recursively find the sum of the integer values of the characters in the word.
Since characters have corresponding integer values from the ASCII table, you are able to sum them into a single integer.
For example, if given “abc”, the method would return 294.
This method has a similar base case to the previous method, but consider what functionality we need in the recursive case.
Step 3: stringClean()
This methods takes one parameter, a string, and returns a “cleaned string” recursively, where adjacent chars that are the same have been reduced to a single char.
For example, passing “yyyyzzzzxxxx” to this method returns a string “yzx”.
Step 4: palindromeChecker()
Given a string, check if it is a palindrome recursively. Return a boolean indicating true if the given word is a palindrome, and false if it is not.
For example, “abcba” would yield true, but “abc” would not.
A word is a palindrome if the letters in the word are symmetric.
Step 5: permutationHelper()
This method is called by the permutation method.
Given a string, return a string that lists all possible permutations of the letters in the string, with spaces preceding, or coming before, each permutation, even the first one.
For example, “123” would give “ 123 132 213 231 312 321”.
The perm parameter keeps track of the current permutation you are creating.
Consider using the a for loop to call the method recursively a certain number of times with different parameters, so you cover all permutations.