Computer Science 2611
Spring 2000
Laboratory Assignment 4
Part 1
Write a function that computes the greatest common divisor
of two nonnegative integers. Start by writing a contract.
Then write the function implementation.
It should use recursion, and should not use a loop.
(The word while should not appear anywhere in this program.)
The gcd function should not change the value of any variable, and
should be written in a simple and elegant way.
Use the following facts.
gcd(0,y) = y
gcd(x,y) = gcd(y mod x, x) (for x > 0)
Write a main program that reads two numbers and prints their
greatest common divisor, by calling the recursive gcd function.
Test your program on several different inputs.
Part 2
The goal of this part is to see what is happening while your program
is running. This kind of thing is very useful for fixing a faulty
program.
Make a copy of your program from part 1, and make modifications to
the copy. Add a global variable (declared outside of any functions)
called cloneIdentity, declared as
follows.
int cloneIdentity = 1;
This is one case where a global variable is justified. This variable
will be used to give a different identity number to each copy of the
gcd function that is created.
Modify the gcd function so that when it starts, it copies the
value of global variable cloneIdentity into a variable that is local to
the function, so that the function can remember its identity. Then
add 1 to cloneIdentity, so that the next copy will get a different
identity.
After getting an identity number, the gcd function should
- print a line clearly identifying itself as the gcd function,
stating its identity, saying that it is starting, and giving the
values of x and y;
- compute the greatest common divisor of x and y using recursion,
as in part 1;
- print a line clearly identifying itself as the gcd function,
stating its identity, saying that it is done, and giving
the values of x and y and the result;
- return the result.
It is not necessary to be verbose. For example, a line showing that
the gcd function is starting might look like this.
gcd # 3: starting, x = 18, y = 42
Run this program on a few inputs to see what is happening.
What to turn in and checklist
Turn in a printout of your program for both part 1 and part 2.
Check each of the following before turning in the program.
- Is the program well indented?
- Is there a clear contract for the gcd function?
- Are you turning in both parts? Part 1 should not have any
extra debug printing in it, but part 2 should have debug printing.
- Is your name, the assignment number and the part number
at the top of each program?
- Is there a comment at the top of the program telling what the
program does?