Computer Science 3300
Spring 2015
Section 001
Programming Assignment 2

Table of contents

1. The assignment
2. Hints
3. A development plan
4. Infinite recursion
5. Submitting your work
6. Late submissions

The Assignment

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

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

Your main function and your function that computes the next number in the sequence should be identical to what the are in assignment 1.

Use the same Makefile as you used for assignment 1.

Hints

Think about how each function can help itself. Here are some suggestions.

1. 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.

2. 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. 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 function, 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?

3. To count the local maxima, create a helper function that takes two parameters, prev and n. It should compute the number of local maxima in the hailstone sequence starting at n, assuming that the value that comes before n is prev. There needs to be a special value for prev that indicates no prior value. Be sure to document your choice for that.

   For example, if the helper function is hailstoneLocalMaximaHelper(prev, n), then hailstoneLocalMaximaHelper(22,11) should return 4. (It counts the number of local maxima in sequence [22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1], from the 11 to the end. The 22 comes before the sequence, so it is no counted.)

   You still need to provide a function that only takes one parameter and yields the number of local maxima. Make it call the helper function.

A Development Plan

Use successive refinement. Here is a plan.

1. Create a directory to hold assignment 2. Copy your program from assignment 1 into that directory. Remove the bodies of the functions that need to be rewritten. Do not remove the contracts or function headings. Do not remove the bodies of next or main. Turn each function with an empty body into a stub. If it returns an integer, just make it return 0. If it does not return an answer, leave the body empty.

2. Write the function that prints the entire sequence. Make sure that it is well indented and readable. Test it. (Note that the results from functions that are only stubs will be 0. That is not a problem at this point.)

3. Write the function that computes the length of the hailstone sequence starting at n. Make sure it is well indented and readable. Test it.

   ---

4. Write the function that computes the largest number in the sequence. Keep it well indented and readable. Test it.

   ---

5. Write the function that computes the length of the longest hailstone sequence for any starting value from 1 to n. Make it well indented and readable. Test it.

   ---

6. Write the function that computes the number of local maxima. Keep it well indented and readable. Test it.

   ---

Infinite recursion

One problem that you might encounter is an infinite recursion, where a function keeps calling itself with the same value until the program runs out of memory. If you run the debugger with an infinite recursion, try to stop the program with control-C before it has produced too many copies of your function. If you do a backtrace and gdb says the run-time stack is corrupt, or that there is no run-time stack, then it means that you have run out of memory. Try slowing down your function by making it write something. Then you will be able to stop it before too many copies have been created. Since you are using successive refinement, you will know which function is at fault. It will be the one that you just added.

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 version (a), log into one of the Linux machines, change your directory to the one that holds your programs, and do the following command.

  ~abrahamsonk/3300/bin/submit 2a hailstone.cpp

  ~abrahamsonk/3300/bin/submit 2b hailstone.cpp

Late submissions

Late submissions on version (a) will be accepted for one day after the due date. Late submissions for version (b) will be accepted for three days after the due date. If you miss a late submission deadline by a microsecond, your work will not be accepted.