Computer Science 2530
Spring 2020
Programming Assignment 3

Table of Contents

1. Purpose of this assignment
2. What you will submit
3. The assignment
4. Additional requirements
5. Things to watch out for
6. Suggestions
7. Infinite recursion
8. Submitting your work
9. Asking questions

Purpose of This Assignment

---

This assignment is intended to familiarize you with recursion.

Read the entire assignment before you start working on it. Be sure to follow the instructions.

What You Will Submit

---

You will need to submit one file called hailstone.cpp.

The Assignment

---

This assignment has nearly the same requirements as assignment 2. Provide exactly the same functions as for that assignment. But for this assignment, do not use any loops at all. Use recursion instead. If you use a loop in a function, you will receive no credit for that function.

Additional Requirements

---

Read the following paragraph twice.

For this assignment, no function is allowed to change the value of any variable, once that variable has been given a value. You will lose a lot of points if you ignore this requirement. If you change the value of a variable with recursion at this point in your studies, it almost always means that you misunderstand recursion.

It is important to define exactly the functions described in the design. Do not try to improve on the design. Do not add extra responsibilities to functions. Do not change the design for any reason. Do not change the names of any of the functions.

All of the functions take exactly one parameter. If you write a function that does not take exactly one parameter, then you will receive no credit for that function.

In most assignments, you are allowed to add extra functions. But for this assignment, you must not add any additional functions. Only write the functions that are required.

You will receive no credit for any required function that depends on an extra function that is not among the required functions.

Do not use

• arrays,
• default parameters,
• call-by-reference,
• global or static variables, or
• the C++ Standard Template Library

for this assignment.

Things to Watch Out For

---

Pay attention to the list of issues in assignment 2. Additionally, avoid creating a variable that is just a copy of another variable. For example, if you have a length function that begins

  int length(int n)
  {
    int m = n;
    …
  }

Suggestions

---

You should be able to keep the same contracts for all of the functions as you had for assignment 2, unless some of them were incorrect. You can also keep the same next and main function from assignment 2, unless they contained errors that need to be fixed or if they change the value of a variable.

Modify the other functions 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.

PrintSequence

Have a special case for n = 1. When n > 1, the sequence contains n followed by the sequence that starts at next(n).

length

Suppose that you want to find the length of the hailstone sequence starting at 7. Notice that next(7) = 22. 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 n = 1 or not.

largest

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 for 7 is clearly the larger of 7 and 52, since 7 is the only number that was not already taken into account in the sequence starting at 22.

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 (since next(52) = 26). The answer is 40. What you want is the larger of 52 and 40.

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. Don't do that.

longestStart

Suppose you want to compute the starting value of the longest sequence starting on a number from 1 to n. Again, the answer is obvious when n = 1. If n > 1, first get the starting value m of the longest sequence starting on a number from 1 to n − 1. Then compare length(n) and length(m). How can you determine the answer from the result of that comparison?

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.

Since you are testing one function at a time, you will know which function is at fault. It will be the one that you just wrote. Inspect it. (You are testing one function at a time, right? What happens to you if you write all of the functions and try to test them all at once?)

If you have an infinite recursion and can't find the problem, use tracing to find out what is happening.

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 xlogin, change your directory for the one for assignment 3, and use the following command.

  ~abrahamsonk/2530/bin/submit 3 hailstone.cpp

Command

  ~abrahamsonk/2530/bin/submit 3

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

Late Submissions

---

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

Asking Questions

---

To ask a question about your program, first submit it, but use assignment name q3. For example, use command

  ~abrahamsonk/2530/bin/submit q3 hailstone.cpp