Lab 2: Recursion with numbers and strings

Problem 1: Powers

• refresh your memory about recursion in Java
• refresh your memory about Java class methods
  (here's a generic Java template)
• use the Java API to format aligned decimals
• start to think about code efficiency
• learn how to print a file from linux
• learn how to capture your program's output for submission (as prof of testing)

In this problem we will use recursion to write a simple Java program that contains a couple of class methods.

1. Create (mkdir) a new folder called lab2 in your labs folder (last week in lab, you created the labs folder). You will be writing all your code from scratch today, so there are no files to download.
2. Inside your lab2 folder, create a new file called Powers.java.
   You can do this one of two ways:
   • emacs Powers.java &
   • start emacs like this: emacs & and then type your file and save (C-x-s) it as Powers.java
3. Add a class method called power() to Powers.java. This method should compute x^n, according to the following recursive definition:

   x^0 = 1.0	for all x
   x^n = x * x^(n-1)	for n>0

4. Add a main() method to your program, and write a few lines of code to invoke power(). Compile and run your program to make sure it works correctly. Think about some good test cases to use!
5. Add one more class method to your program, called morePower(), to compute x^n according to the following alternative definition:

   x^n = x^(n/2) * x^(n/2)	for even values of n
   x^n = x * x^(n/2) * x^(n/2)	for odd values of n

6. Test morePower() (here is a mere wisp of a start of testing)
7. Format the output so it looks good (check out the DecimalFormat class in the Java API)

If you had to choose between the two implementations above, which one would you prefer? Why? Write your answer in the comments of the method.

Printing from Linux

Capturing your program's output in a file: Redirect in linux

Problem 2: Working with Strings

• refresh your memory about programming with strings in Java
  (link to Java API String Class)
  (link to Lecture notes on Recursion & Strings)
• write code using command-line input
• offer your user multiple options when running your code
• handle incorrect or incomplete user-input

   racecar    stella won no wallets    noel sees leon
   no mists or frost simon    never odd or even

• Write a class LabStringUtilities (in a new file called LabStringUtilities.java).
• Write a class method called printPhrase that, given a string s, prints the string recursively, one character at a time (see example below). Test this method by calling it from within your main method. Program output is shown in orange if the statement printPhrase("penguins"); is included in the main method.

  [cs230@puma lab2] java LabStringUtilities
  p
  e
  n
  g
  u
  i
  n
  s
  

• Write a public class method called isPalindrome() in your LabStringUtilities class. This method takes a String as an argument, and returns a boolean value indicating whether the input string is a palindrome or not. As a reminder, a string is a palindrome if it reads the same from left to right as it reads from right to left.

  In the main() method of your class, add code to test the isPalindrome(). For easier testing, the argument to isPalindrome() can come as a command-line argument, i.e. by accessing the contents of args[0] from within your main() method.

  Test your method many times. Is it easier to test this method, with its command-line argument, or the ones in the Powers problem above?

• Create a class method in your LabStringUtilities class that, given a String s, returns a string obtained from s by removing all vowels. You can call this method removeVowels. For example, calling the method on "i love cs230" should return the string "lv cs230" and "let me know" should return "lt m knw." Provide some testing code for this method.
• Create another class method that, given a string s, returns the string obtained from s by replacing each blank in it with a '_'(underscore). Name this method replaceSpaceWithUnderscore. Test your method (more than once ;-)).
• Add instructions in your main() method that allow the user to choose from three options:
  
  1. test if string is a palindrome
  2. remove all vowels from string
  3. replace blanks with underscores

• [cs230@cs] java LabStringUtilities "I like to do somersaults" 2
  lk t d smrslts
• [cs230@cs] java LabStringUtilities "Houston, we have a problem." 3
  Houston,_we_have_a_problem.
• [cs230@cs] java LabStringUtilities "otto sees otto" 1
  "otto sees otto" testing for palindrome: true
• [cs230@cs] java LabStringUtilities "otto sees otto eating a banana" 1
  "otto sees otto eating a banana" testing for palindrome: false
• [cs230@cs] java LabStringUtilities "otto sees otto" 3
  otto_sees_otto
• [cs230@cs] java LabStringUtilities
  Program needs a string to be tested and the method to test (1: pali; 2: vowels; 3: underscore)

Problem 3: Play with Digits (optional)

• Recursion practice
• Processing user-supplied input

• Write a class DigitPlay that contains a public class method called numDigits(). This method takes a positive integer as an argument, and counts and returns the number of digits in the input number. For example, if the method is passed the number 123456 as argument, it should return 6, since there are 6 digits in the input number.
• Add another method to your class, called sumDigits() that, again takes a positive integer as an argument and returns the sum of the digits in the input number. For example, if the method is passed the number 123456 as argument, it should return the integer 21, since 1+2+3+4+5+6 = 21. The definition of this method will be very similar to the numDigits() one.

  Both of the above methods should be defined recursively. As always, test each method as soon as you define it, before you proceed to add more code to your program.

• Most identification numbers, such as the ISBN number on books or the Universal Product Code (UPC) on grocery products or the identification number on a traveler’s check, have at least one digit in the number that is a check digit. The check digit is used to detect errors in the number. The simplest check digit scheme is to add one digit to the identification number so that the sum of all the digits, including the check digit, is evenly divisible by some particular integer. For example, American Express Traveler’s checks add a check digit so that the sum of the digits in the id number is evenly divisible by 9. United Parcel Service adds a check digit to its tracking numbers such that a weighted sum of the digits (some of the digits in the number are multiplied by numbers other than 1) is divisible by 7.

• Add one more method to your DigitPlay program, called validateNumber() that takes a positive integer, and determines if it is a possible AMEX Traveler’s check id number. (Question: If the sum is indeed divisible by 9, can you tell for sure that the input number is a correct AMEX Traveler’s check id number?)

• Test, test, test your code.