Purpose of This Assignment

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.

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

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

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;  } 

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

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

I currently have this code which uses loops and i need to covert the loops to recursions

#include using namespace std;

// Next(n) returns the number that follows n in a hailstone sequence. // For example, next(7) = 22 and next(8) = 4. // // Next requires n > 1, since there is no number that follows 1. int next(int n) { int x = n; if (x % 2 == 0) { return (x / 2); } else { return (3 * x + 1); } }

//writeHailstoneSequence(n) //prints the entire hailstone sequence to //the standard output void writeHailstoneSequence(int n) { for(int x = n; x > 1; x = next(x)) { printf("%i ", x); } printf("1"); }

//lengthHailstone(n) returns //the length of the entire //hailstone sequence starting at n. int lengthHailstone(int n) { int length = 1; int x = n; while (x > 1) { x = next(x); length++; } return length; }

//largestHailstone(n) returns //the largest value of the sequence //starting at n. int largestHailstone(int n) { int large = n; int x = n; while (x != 1) { if (large <= x) { large = x; } x = next(x); } return large; }

//largestLengthHailstone reutrns //the largest possible length in the //sequence from 1 to n. int largestLengthHailstone(int n) { int x = n; int length = lengthHailstone(x); if (x == 1) { return 1; } while (x > 1) { if (length <= lengthHailstone(x)) { length = lengthHailstone(x); } x = x - 1; } return length; }

//sequenceLargestValue(n) returns //largest value in the hailstone //sequence that starts with a value //of 1 to n. int sequenceLargestValue(int n) { int x = n; int sLarge = largestHailstone(x); if (x == 1) { return 1; } while (x > 1) { if (sLarge <= largestHailstone(x)) { sLarge = largestHailstone(x); }