Functions and Pointers

Summary

You will write a program to reduce fractions using a recursive version of Euclid's algorithm.

Objectives

Compare functional and iterative approaches while reinforcing how to use pointers to return and modify values.

Problem

In the last homework, you implemented a stand-alone program to calculate the greatest common divisor (GCD) of two positive integers using an iterative (or loop-based) version of Euclid's algorithm. The GCD may also be used to reduce fractions

Recursive GCD

You may have noticed that the algorithm can be expressed in a recursive fashion as well. (Step 2 represents the base case test and value, while Step 3 represents the recursive call to Step 1's recursive case work.)

Implement Euclid's algorithm recursively with the following function.

unsigned long gcd(unsigned long m, unsigned long n)

You should only write a single function to solve this problem and no loops.

Reducing Fractions

As noted above, the GCD is needed to reduce fractions. Use your gcd function to place appropriate reduced values in the pointer arguments of the following function.

void reduce(long numerator,
            unsigned long denominator,
            long *reduced_numerator,
            unsigned long *reduced_denominator)

Note that the numerator may be signed. Your algorithm should handle negative and improper fractions appropriately.

General Notes

• Your procedures should be well-documented with pre- and post-conditions.
• Your procedures should appear in a program adequately testing them according to a complete and well-structured test plan.
• Your programs should use assert to verify any preconditions.

Grading

In addition to the general grading guidelines for evaluation, the assignment is worth 20 points.

• Comments on Program Format, Comments, Readability, etc.
  (Points not given, but points can be deducted.)
• [2 points] Functions give clear and complete pre- and post-conditions
• [2 points] Assertions verify pre-conditions
• [4 points] Correctly computes GCD recursively
• [1 point] Calculates the remainder of dividend and divisor
• [1 point] Recursion terminates when remainder is zero
• [2 point] Repeats steps with an appropriate recursive call
• [5 points] Correctly reduces fractions
• [2 points] Utilizes gcd to find reduction factor
• [2 points] Handles negative fractions correctly
• [1 points] Returns values via pointer dereferences
• [7 points] Tests demonstrate correctness
• [2 points] Test plan enumerates the range of problem circumstances
• [3 points] Test cases include specific inputs and expected outcome(s)
• [1 point] Transcripts demonstrate functionality with test runs
• [1 point] Statement argues why the program is correct

A five point penalty will apply to any submission that includes personally identifying information anywhere other than the references/honesty file.