ITPEC FE Morning April 2019 Question 7

31 — f is Euclid's algorithm, so f(775, 527) is the greatest common divisor of 775 and 527.

Each call replaces (x, y) with (y, x mod y) until y is 0:

• •f(775, 527): 775 − 527 = 248, so the call is f(527, 248)
• •f(527, 248): 527 − 2 × 248 = 31, so the call is f(248, 31)
• •f(248, 31): 248 = 8 × 31, remainder 0, so the call is f(31, 0)
• •f(31, 0): y = 0, return 31

Check: 775 = 25 × 31 and 527 = 17 × 31, and 25 and 17 share no factor.

Answer (b)

Why not others:

• •(a) 0 — the value of y when the recursion stops, not the value returned, which is x
• •(c) 248 — the first remainder; stopping after one step skips the remaining calls
• •(d) 527 — the original second argument, which does not divide 775

Key rule: A function of the form "if y = 0 return x, else recurse on (y, x mod y)" is Euclid's GCD; trace the remainders until one is 0 and return the last nonzero value.

Algorithm and Programming · AI-written, may contain errors