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.

It's a good idea to have a labs directory in your account. You can put all your labs from the semester in this folder. Create a labs directory, and then create a subdirectory named lab2, under your labs directory, and make it your working directory, as shown below. You can move your lab1 folder from last week into your labs folder as well.

Then follow these steps:

1. Create a new file called Recurse.java.
   You can do this one of two ways:
   • emacs Recurse.java &
   • start emacs like this: emacs & and then type your file and save (C-x-s) it as Recurse.java
2. If your Java is a bit rusty, you can use this template as a guide
3. 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

    

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.

When you are done, just for practice with the submit command, submit your Recurse.java program electronically by executing the following command, while still in your lab2 directory:

submit cs230 powers *.*

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

  So then the usage would be something like:
  java LabStringUtilities "I like to do somersaults" 2

  would result in this output:
  lk t d smrslts

Problem 3: Play with Digits

                         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