Introduction
This lab is intended to help you THINK clearly about recursion. It is more about THINKING than CODING. The actual code for the first two tasks is not extensive. If you find yourself writing lots of code, you've likely gone astray in your thinking. The third and fourth tasks will require a bit more coding, but still not a lot.
Specific requirements
- For each task, submit working java code that implements recursive methods and performs according to specification.
- Public methods should exactly match specification below for name, return type, and arg type(s)
- Methods should throw exceptions if appropriate. Throw an exception only if the caller is responsible for the exceptional situation. Note that this will *not* include type errors for the args, since the compiler will catch those.
- All code should be properly documented with javadoc-format comments. Include javadoc comments for each class, each method, and each data member.
- Generate html documentation using the javadoc command (See me or a peer if you need help with javadoc)
- Include an lab report (*.doc format). The report should begin with a cover page, followed by four main sections (one for each of the four tasks). Each of the four sections should have the following:
- Problem Statement
- Prose description of the algorithm
- Code (for the relevant method only -- don't include the tester code in your lab report)
- Transcript of successful run showing solution of a full range of examples (including exceptions).
- <optional> Discussion of any difficulties or interesting things you noticed.
Task 1
Write a java program to perform multiplication by recursively calling a method that uses addition.
public long multiply(long x, long y) {...}
Example of logic: (5*4) == (5 + (5*3)) == (5 + (5 + (5*2))) == (5 + (5 + (5 + (5*1)))) == (5+5+5+5) == 20
Carefully consider what special cases might be needed (one example, what if one of the arguments is 0?). Include a main() method that demonstrates how it works with several different values, including at least one example of each special case. Output should include at least the problem being solved as well as its solution.
Task 2
Implement exponentiation using a recursive approach.
public long power(long base, int exponent) {...}
Example of logic: 5^4 == 5*(5^3) == 5*(5*(5^2)) == 5*(5*(5*(5^1))) == (5*5*5*5) == 625
Consider carefully what special cases might be needed (one example, what if one of the arguments is 0?) Include a main() method that demonstrates how it works with several different values, including at least one example of each special case. Output should include at least the problem being solved as well as its solution.
Task 3
Implement Euclid's algorithm for finding the greatest common divisor of two positive integers.
public int gcd(int x, int y) {...}
See the problem description for PP 7.1 in the text, page 205. Consider carefully what special cases might be needed. Include a main() method that demonstrates how it works with several different values, including at least one example of each special case. Output should include at least the problem being solved as well as its solution.
Task 4
Write a java program using recursion to check a string to see if it is a palindrome.
public boolean isPalindrome(String phrase) {...}
Ignore punctuation, capitalization, spaces, and any other non-alphabetic characters -- in other words, remove them from the string before checking. (thus a phrase like "Madam, I'm Adam" should be ruled a palindrome, even though it's precise reverse would be the nonsensical "madA m'I ,madaM") Then use the following logic to check for palindromicity: the empty string is a palindrome; any single alphabetic character is a palindrome; a string a$b is a palindrome if a==b and $ is a palindrome. Note: use recursion rather than iteration.
Write a main method that repeatedly prompts the user for input, checks whether the input is a palindrome, and informs the user of the result. Terminate if the user enters a single period '.' as the input. The user prompt should notify the user of this special termination char.
Submission
- Submit your assignment as a single .zip archive file titled LAB06_lastname.zip. It should include working, documented java code as well as the lab report.
- Submit via sakai.messiah.edu | COSC282 | Assignments | Lab06.