ITPEC FE Morning October 2018 Question 7

Euclidean Algorithm (GCD via Recursion) — computing the greatest common divisor using a recursive function with mod.

The function F(x, y) is defined as:
- F(x, y) = x, when y = 0
- F(x, y) = F(y, x mod y), when y > 0

This is the classic Euclidean algorithm for finding the GCD.

Trace F(231, 15):
- F(231, 15) → y > 0 → F(15, 231 mod 15) = F(15, 6)
- F(15, 6) → y > 0 → F(6, 15 mod 6) = F(6, 3)
- F(6, 3) → y > 0 → F(3, 6 mod 3) = F(3, 0)
- F(3, 0) → y = 0 → return 3

Why not others:
- (a) 2 — incorrect remainder chain
- (c) 5 — incorrect remainder chain
- (d) 7 — incorrect remainder chain

Key rule: A recursive function with base case y = 0 returning x, and recursive case F(y, x mod y), is the Euclidean algorithm — it always returns GCD(x, y).

AI-generated — may contain errors