Assignment 03

Task

Write both an iterative and a recursive version of 5 methods in order to practice recursion and understand its parallels to loops.

Text: 5.1-5.2
Concepts: Recursion.

Steps

You will submit two separate files for this assignment. UsernameA03i.java will contain the iterative versions of your methods and UsernameA03r.java will contain the recursive versions. For the iterative version, you should use at least one loop in each method and no method should call itself. For the recursive version, you should not use any loops anywhere in the file and each method should call itself.

The methods and the documentation of what they should do are as follows:

/**
 * Returns a String containing the given number of * characters.  
 * <p>
 * If width is 0 or more, the returned String will end with a newline ('\n')
 * character.  If width is negative, returns the empty string "".
 * <p>
 * Examples:
 * <pre>
 * row(3)  -> "***\n"
 * row(5)  -> "*****\n"
 * row(0)  -> "\n"
 * row(-2) -> ""
 * </pre>
 *
 * @param width  How many *s should be in the generated row
 * @return       A String containing width *s and a \n
 */
public static String row(int width)


/**
 * Returns a String of *s that form a right triangle of the given size.
 * Both the width and height will be equal to the given size.  The right
 * angle of the printed triangle will be in the lower-left.
 * <p>
 * If size is 0 or less, returns the empty String "".
 * <p>
 * Examples:
 * <pre>
 * triangle(6)  -> "*\n**\n***\n****\n*****\n******\n"
 * triangle(3)  -> "*\n**\n***\n"
 * triangle(1)  -> "*\n"
 * triangle(0)  -> ""
 * triangle(-2) -> ""
 * </pre>
 * <p>
 * In these examples, '\n' is a single newline characters.  If these 
 * strings were printed, they would result in multiple lines of output.
 *
 * @param size  The width and height of a right triangle of *s
 * @return      A String that contains the complete triangle, including
 *              necessary line breaks ('\n')
 */
public static String triangle(int size)
  //HINT: To avoid loops, reuse your row method above to generate each line 
  // of the triangle


/**
 * Returns a String containing the given String fragment repeated the given
 * number of times with a decreasing count placed between the fragments. 
 * That is, the format of the returned string is frag#frag#frag here # is 
 * the sequences of decreasing integers from (times-1) to 1.  (See examples 
 * for more.)
 * <p>
 * If times is 0 or less, returns an empty string "". 
 * <p>
 * Examples:
 * <pre>
 * interpose"ho", 3)     -> "ho2ho1ho"
 * interpose("yes", 5)    -> "yes4yes3yes2yes1yes"
 * interpose("", 5)       -> 4321
 * interpose("x", 1)      -> "x"
 * interpose("raise", -1) -> ""
 * </pre>
 *
 * @param str    The string to repeat
 * @param times  How many times to repeat it
 * @return       A String containing str x times with a decreasing count
 *               between the repeated strs.
 */
public static String interpose(String str, int times)


/**
 * Sets the cells within a section of the given array equal to i*i, where i 
 * is the index of the containing cell.  That is, starting at i = startIndex,
 * sets array[i] equal to i*i, and then repeats this for all higher i up to
 * the end of the array.
 * <p> 
 * Changes the given array, but also returns a reference to it.
 * If start index is outside the bounds of the array, this method does 
 * nothing, returning the array unchanged.
 * <p>
 * Examples:
 * <pre>
 * squares(new int[5], 2)     -> [0, 0, 4, 9, 16]
 * int[] nums = {2, 4, 6, 8, 10};
 * squares(nums, 6)           -> [2, 4, 6, 8, 10]
 * squares(nums, 3)           -> [2, 4, 6, 9, 16]
 * </pre>
 *
 * @param array       The array of ints to change
 * @param startIndex  The index within array at which to start writing 
 *                    squares
 * @return            The same array given as a parameter
 */
public static int[] squares(int[] array, int startIndex)

  
/**
 * Uses the Euclidean algorithm to compute the greatest common divisor 
 * of the given two integers.  In other words, assuming |a| >= |b|:
 * <pre>
 * gcd(a, 0) == a, or
 * gcd(a, b) == gcd(b, a - (b * (a/b)))
 * </pre>
 * <p>
 * When calling this method, the parameter a does not need to be >= b
 * because this method will appropriately reorder the parameters' values 
 * if necessary. The returned value will always be >= 0.
 * <p>
 * Examples:
 * <pre>
 * gcd(48, 32)  -> 16
 * gcd(32, 48)  -> 16
 * gcd(32, 32)  -> 32
 * gcd(0, 32)   -> 32
 * gcd(9, 17)   -> 1
 * gcd(18, -6)  -> 6
 * gcd(-6, -18) -> 6
 * </pre>
 * 
 * @param a  One of the two values to find the GCD of
 * @param b  The other of two values to find the GCD of
 * @return   The positive GCD of a and b
 */
public static int gcd(int a, int b) 
  // HINT: Use Math.abs and compare the values of a and b and 
  // swap their  values if |a| < |b|.  After that point, you'll know
  // that |a| >= |b|.
  

Tamarin will be calling your methods directly, so you must exactly match the method signatures given above. I strongly recommend you copy the whole section above (including documentation) and start from there.

Note that none of these methods should print anything. They all return their results instead.

Sample Output

This assignment requires no output. However, you may want to use the main method of each of your classes to do some testing. Call your methods with some sample values, print the results, and make sure the results are correct. (See the FAQ on testing for more.)

What to Submit

Upload your UsernameA03i.java and UsernameA03r.java files to Tamarin. This will require two separate submissions to Tamarin.

Remember to follow the course coding standards on all assignments.

Grading [50 points] (2 parts)

2 - UsernameA03i.java compiles
20 - UsernameA03i.java correctness
4 points each for the methods required above. They must use iteration to perform as documented. (-10 if you do not use at least one loop per method.)
3 - UsernameA03r.java compiles
25 - UsernameA03r.java correctness
5 points each for the methods required above. They must use recursion to perform as documented. (-10 if your A03r file contains any loops at all, even in main.)

FAQs

Why do the methods support all this extra stuff I'm never going to use, like negative arguments?

It is unlikely that anyone is going to want to print a negative-size triangle. However, whenever you write a method (or a program that accepts input), you need to consider the full range of possible inputs you could receive. Even if your method is defined to work with only a subset of that range, you should think about what the method will do if it is given an illegal value. A good method's behavior is always well-defined. It should not crash or throw an undocumented exception. For that reason, I'm defining what your methods should do for all possible input values.

Footnote: Well, technically I left out null. It's possible to pass null to any method that takes an object or an array. However, since it is so common for this to cause a NullPointerException as soon as the method tries to use that object, I didn't document that behavior here. As an example of this convention, see the String class in the API: They just mention in the general class description that "passing a null argument to a constructor or method in this class will cause a NullPointerException to be thrown" and leave it at that.

Are we supposed to be documenting all of our methods like this?

Yes, you should have a /** javadoc */ block like this before every class and method you write.

For classes, you should give a short overview (one or two sentences) of the purpose of the class.

For methods, you should describe what parameters it takes, what it returns, and what the method does (depending on the parameters). If the method has any side-effects, such as printing to the screen or changing any instance or class variables, those effects should be mentioned too. It is good practice to have the first sentence of your description be an overall summary, since this first sentence is extracted as the short description of the method. You are encouraged to use @param and @return tags as shown here, but these are not required. You don't usually need to provide examples in your own documentation, either. See the course coding standards for a link about writing good javadocs.

You should also know how to extract the javadoc documentation. For example, here's the documentation for my ZtomaszeA03r.java. Note how the @param and @return tags get special formatting, and how the <p> and <pre> tags I used control the formatting so everything doesn't collapse into one big paragraph.

Javadoc comments go immediately before the start of any class or method they refer to. They should describe what the method does, not how it does. For example, note that the method documentation given here does not mention loops, recursion, or any local variables; that would all be implementation-level details.

Inside the body of a method, you should use //comments to describe any tricky code details or give implementation level details. (You can also use /* comments */, though I personally save those for when I want to comment out a chunk of code while debugging.)

Sadly, the value of comments and documentation are not always obvious until you hit the Maintenance phase of a project, which you never do with most of these assignments. But documenting is still a very important habit to develop. Ask any programmer who has ever had to change some else's code or had to return to some uncommented code they wrote more than a month ago and see what they tell you about comments. :)

Is there something special we're supposed to do to test our code?

Testing is an extremely important programming skill. As discussed in lecture 02A, validating that your implementation meets the initial requirements is always a step in any respectable software development model. You should definitely know how to do this yourself (and not just rely on Tamarin to do it for you).

The first step to testing is to decide what tests to write. For example, consider a method named square that is supposed to take a int between 1 and 10 and return its square. If the given int is not in that range, the method should return 0. (This is just an example, not one of the methods you have to write for this assignment.)

Now, it's not really possible to test every possible input value to this method, which would be over 4 billion different int values. So what you can do instead is identify input equivalence classes. Then run one test for each equivalence class.

The square method is supposed to work with digits between 1 and 10. So pick a value in there, such as 3, and determine what the correct return value should be. square(3) should return 9, so try that and see if that's what the method actually returns.

The square method would likely execute the same logical code path for every digit between 1 and 10, so adding more tests in this same range doesn't really tell you more. For example, testing square(4), square(5), and square(6) will not likely reveal any bugs over what the single square(3) test already covered.

However, the method is only supposed to work with digits between 1 and 10, which means you need to test ints not in that range. That's actually two ranges: <= 0 and > 10. So you could test square(-3) and square(12), for example, and make sure you get the appropriate 0 return value in each case.

The border cases between equivalence classes are actually the most likely place for bugs to occur, though. For example, it's very easy to be off-by-one if you typed < when you meant <=, or vice versa. So even better tests for this method than 3, -3, and 12 would be 0, 1, 10, and 11. This tests both sides of the two boundary points. (I would probably throw in a test in the middle too, such as 5, but it's not really necessary.) But by wisely selecting only these 4 or 5 test cases, we can be fairly confident that we have sufficiently tested this square method. I say "fairly confident" because, while testing can prove the presence of bugs, it can never prove their absence (a paraphrase of Dijkstra).

Once you decide what tests you want, the simplest way to do write them would be something like this:

  System.out.println(square(-1) == 0);
  System.out.println(square(1) == 1);
  System.out.println(square(10) == 100);
  System.out.println(square(11) == 0);

(If comparing strings, remember to use .equals, not ==. If comparing arrays, consider using the java.util.Arrays.equals method.) When executed, this should print a bunch of trues to the screen. If a false appears, it means one of the tests failed and you can check which one.

This is a primitive way to test, but it's sufficient. As the number of tests build, it's nice to be able to see some output for each test explaining what exactly was tested and what the expected and actual values were. To get this output, it's handy to write a static helper test method so that you can still write each test in a line or two.

There is also a commonly used library called JUnit that provides a number of such helper methods that make it easier to write quick tests. We may cover that in more detail later in the term.

If I call triangle(3), should it print *\n**\n***\n on one line or *, **, and *** on 3 separate lines?
None of these methods should print directly to the screen. They should all return a String instead. triangle(3) should return the string "*\n**\n***\n". When you then print this string to the screen, it will span 3 lines.

For example, suppose you did this in main:

  triangle(3);                       //line 1
  System.out.println(triangle(3));   //line 2

Line 1 should generate no output and so would appear to do nothing. Line 2 would print this to the screen:

*
**
***

(Note that if you actually wanted *\n**\n***\n to show up on the screen, you'd have to return the String ""*\\n**\\n***\\n". Don't do that.)