Lab 10: Recursion
Due Date and Submission Requirements
- Due Date: Tuesday, April 8th at 11:59 p.m.
- Partner Information: This is an individual assignment. You are allowed to collaborate with other students, but each student must submit their individual, independent solution.
- Submission Instructions: You will submit your Lab10.java to the appropriate D2L dropbox
- If you are in Andras's section, please also copy and paste your code into the D2L submission text box
The goal of this lab is:
- Gain experience using recursion
Directions
You will download Lab10Demo.java as a starting point. Your program should print all palindromes that can be made from a list of characters (characters), which is an ArrayList of Strings. A palindrome is a word that is spelled the same forwards and backwards (ex. racecar, ABBA, tacocat). You are going to do this by generating all permutations of the string that can be made from the characters, and then checking to see if each word is a palindrome. You are going to write two recursive methods:
generate_permutations(???)- This method will generate all permutations from a list of characters that is defined in the main method. We wrote some of this in class last Wednesday, however that implementations does not allow for repeated characters, which we must allow here. This will require you to change some of the code from Wednesday. Consider adding a boolean[] array as a parameter to this method, where array[i] represents if character at index i from the list of characters has been used in the string. You must use recursion here.
isPalindrome(String word)- Given a string, this method will return true if a word is a palindrome, and false if the word is not a palindrome. This method must use recursion. Consider looking at the first character and last character of the word, and then recursively calling the method with the "middle" word. You may find the Java substring String method to be helpful here.
Starting Code
Output
When you run your program, your output should look exactly like this screenshot
Grading (10 points)
- generate_permutations correctly generates all permutations- 4 points
- isPalindrome correctly identifies if a word is a palindrome or not- 4 points
- Recursion was used in each method- 2 points
Penalties
- Recursion not used -10 points