Lab 2: Recursion with numbers and strings

Problem 1: Powers

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

• Create a new folder called lab2 on your Desktop/labs folder (remember to upload it to the server into your labs folder at the end of lab). You will be writing all your code from scratch today, so there are no files to download.
• Inside your lab2 folder, use DrJava to create a new file called Recurse.java.
• Here is a generic Java template that shows how to set up class methods.
• Add a class method called power() to Recurse.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

• 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!
• 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

• Test morePower() (here is a mere wisp of a start of testing)
• 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.

Problem 2: Working with Strings

• Write a class LabStringUtilities (in a new file called LabStringUtilities.java), that contains a public class method called isPalindrome(). 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 Problem1?

• Add a class method, to your LabStringUtilities, that, given a String s, returns a string obtained from s by removing all vowels. For example, calling the method on "i love cs230" should return the string "lv cs230". Provide some testing code for this method.
• Add one more class method that, given a string s, returns the string obtained from s by replacing each blank in it with a '_'(underscore). Test your method.
• 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

• > java LabStringUtilities "I like to do somersaults" 2
  remove vowels: lk t d smrslts
• >java LabStringUtilities "Houston, we have a problem." 3
  replace space w/ underscore: Houston,_we_have_a_problem.
• > java LabStringUtilities "otto sees otto" 1
  check palindrome: "otto sees otto" : true
• > java LabStringUtilities "otto sees otto eating a banana" 1
  check palindrome: "otto sees otto eating a banana" : false
• > java LabStringUtilities "otto sees otto" 3
  replace space w/ underscore: otto_sees_otto
• > java LabStringUtilities
  Program needs a string to be tested and the method to test (pali, vowels or underscore)

Problem 3: Play with Digits

• 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?)

Problem 4: Pascal's Triangle

                         1
                     1       1
                  1      2      1 
               1     3       3     1
            1     4      6      4     1
         1     5     10      10    5     1
      1     6     15     20     15    6     1
   1     7     21    35      35    21    7     1
1     8     28    56     70     56    28    8     1