Euclid's algorithm computes the greatest common divisor (gcd) by preserving the gcd while replacing the input pair with smaller values. For positive integers with a ≤ b, gcd(a,b) = gcd(a,b % a). section 7.3
Recursive C implementation
The recursive function asserts a ≤ b, returns b when a is zero, computes b % a, and recurses with the remainder and a. Starting with 18 and 30 produces the successive pairs (18,30), (12,18), (6,12), and (0,6), yielding 6. section 7.3
TAKEAWAY:
- Replace the larger operand with the remainder after division by the smaller operand; the gcd remains unchanged. section 7.3
- Treat the displayed function as a partial interface: it assumes positive inputs and an ordered pair. section 7.3
