| Assigned: | Monday, February 4 |
| Due: | Friday, February 15, 11:59pm |
| Points: | 400 |
This assignment is intended to familiarize you with recursion.
Because the functions and contracts in this assignment are the same as those assignment 2, the contract bonus is not available for this assignment.
This assignment has nearly the same requirements as assignment 2. Provide exactly the same functions. 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.
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. Pay attention to this! 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 are not on the right track.
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.
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.
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
Do not use arrays, default parameters or call-by-reference. Do not use any features of the C++ Standard Template Library.
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;
…
}
then you have created a variable m that is just another
name for n. Remember that you can't change either of
m and n. Having two names for the same thing
just confuses things. Don't do that.
| Suggestions |
|---|
|
1. Create a directory to hold assignment 3. Copy files hailstone.cpp, Makefile and dotest assignment 2 to the assignment 3 directory. Edit the comments at the top of hailstone.cpp to say that this is assignment 3. You should be able to keep the same contracts, 'next' function and 'main' function from assignment 2, unless they contained errors that needed to be fixed. If necessary, edit those functions so that they do not change the value of any variable, once the variable has a value. |
|
2. 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. |
|
3. Modify the function 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. 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. |
|
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 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: 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 97. Does it respond quickly, or is it really slow? Try it on a few larger numbers, say around 1000. |
|
6. Suppose you want to compute the length of the longest sequence starting on a number from 1 to n. If n = 1, the answer is obvious. If n > 1, first get the length k of the longest sequence starting on a number from 1 to n − 1. Then compute the larger of length(n) and k. |
|
7. 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? |
One problem that you might encounter is an infinite recursion, where a function keeps calling itself with the same value until it 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. (What happens to you if you wrote all of the functions and are trying to test them all at once? You end up in the swamp. Not a good idea.)
If you run gdb 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.
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
After submitting, you should receive confirmation that the
submission was successful. If you do not receive confirmation,
assume that the submission did not work.
Command
~abrahamsonk/2530/bin/submit 3
will show you what you have submitted for
assignment 3.
You can do repeated submissions. New submissions will replace old ones.
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.
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
Then send me an email with your question. Do not expect
me to read your mind. Tell me what your questions are.
I will look at the file that you have submitted as q3.
If you have another question later, resubmit your new file
as assignment q3.