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

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

  2. compute the greatest common divisor of x and y using recursion, as in part 1;

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

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

  1. Is the program well indented?

  2. Is there a clear contract for the gcd function?

  3. Are you turning in both parts? Part 1 should not have any extra debug printing in it, but part 2 should have debug printing.

  4. Is your name, the assignment number and the part number at the top of each program?

  5. Is there a comment at the top of the program telling what the program does?