| Assigned: | Tuesday, September 13 |
| Due: | Wednesday, September 21, 11:59pm |
This assignment is intended to familiarize you with recursion.
It is important to define exactly the functions described in the design. Do not try to improve on the design. Do not change the design for any reason.
With a single difference, this assignment has the same requirements as assignment 1. Provide the same functions. The difference is: for this assignment, do not use any loops at all. Use recursion instead. If you use a loop in one of the functions, you will receive no credit for that function.
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.
| Suggestions |
|---|
|
1. Create a directory to hold assignment 2. Copy your hailstone.cpp and Makefile files 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 function and main function from assignment 1. Make sure that those functions do not change the value of any variable, once the variable has a value. If they do, modify them. |
|
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. 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 for 7 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 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? Try it on a few large4 numbers, say around 1000. |
|
6. To compute the starting value of the longest sequence starting on a number from 1 to n, where n > 1, first get the starting value m of the longest sequence starting on a number from 1 to n−1. Then compute the larger of length(n) and length(m). |
|
7. Read the Nonfunctional requirements of assignment 1. They also apply to assignment 2. Also remember not to change the value of any variable, once it has a value. |
One problem that you might encounter is an infinite recursion, where a function keeps calling itself with the same value until the it 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 testing one function at a time, you will know which function is at fault. It will be the one that you just added.
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,
use the following command.
~abrahamsonk/2530/bin/submit 2 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 2
will show you what you have submitted for
assignment 2.
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.