Computer Science 3200
Fall 2015
Section 001
Programming Assignment 2

Table of contents

1. The assignment
2. Suggestions
3. Submitting your work

The Assignment

---

This assignment has the same requirements as assignment 1. Provide the same methods. However, for this assignment, do not use any loops at all. Use recursion instead.

For this assignment, no method is allowed to change the value of any variable, once that variable has been given a value.

Suggestions

---

1. Create a directory to hold assignment 2. Copy your hailstone.java file from assignment 1 to the assignment 2 directory. Edit the comments at the top of the program to say that this is assignment 2.

   You should be able to keep the same contracts, next method and main method from assignment 1.

   
   

2. Modify the other methods so that they use recursion instead of loops. Modify them one at at time, and test each one after modifying it. Do not try to modify them all then test them all together. The remaining items give some hints.

   
   

3. Modify the method that prints the entire sequence. Include a special case for n = 1. When n > 1, the sequence that starts at n contains n followed by the sequence that starts at next(n).

   
   

4. Suppose that you want to find the length of the hailstone sequence starting at 7. If you ask for the length of the hailstone sequence starting at 22 (result: 16), how would you determine the length of the sequence starting at 7?

   Handle the length of the sequence starting at 1 as a special case. Use an if-statement to decide whether this is the special case of 1 or not.

   
   

5. Suppose that you want to know the largest number in the sequence starting at 7. Ask for the largest number in the sequence starting at 22. (The answer is 52). The largest number is clearly the larger of 7 and 52, since 7 is the only number that was not already taken into account. As another example, suppose that you want to know the largest number in the sequence starting at 52. Ask for the largest number in the sequence starting at 26. The answer is 40. What you want is the larger of 52 and 40, clearly 52.

   Important Note. In terms of efficiency, recursion acts as an amplifier. Algorithm designers use it because, if they think of a clever idea and they use it in a recursive definition, recursion amplifies it into a very efficient algorithm. But recursion also amplifies bad ideas. If you do something in a slopply way in a recursive method, recursion can amplify it and make a very slow algorithm. In particular, if you do the same recursive call twice, which is a waste of time, recursion will be very slow. Try your program on input 31. Does it respond quickly, or is it really slow? Try it on a large number.

   
   

6. To compute the starting value of the longest sequence starting at a number from 1 to n, you will find yourself recomputing length(k) for the same value k repeatedly. Don't worry about that. Later on we will see how that could be avoided.

   
   

7. Read the Nonfunctional requirements of assignment 1. Also remember not to change the value of any variable, once it has a value.

Submitting your work

---

You must submit your program using the following method. Email submissions will not be accepted. An excuse that you do not know how to use Linux will not be accepted.

To turn in your work, log into the Linux system, change your directory for the one for assignment 2, and use the following command.

  ~abrahamsonk/3200/bin/submit 2 hailstone.java

Command

  ~abrahamsonk/3200/bin/submit 2

You can do repeated submissions. New submissions will replace old ones.

Late submissions

Late submissions will be accepted for one day after the due date. If you miss a late submission deadline by a microsecond, your work will not be accepted.