ITPEC FE Morning April 2019 Question 7
ITPEC FE Morning April 2019 — Question 7 of 80
Euclidean Algorithm (GCD via Recursion) — recognizing and tracing the classic recursive GCD function.
The function f(x, y) implements the Euclidean algorithm: if y = 0, return x; otherwise, recurse with f(y, x mod y). This computes the greatest common divisor (GCD) of x and y.
Trace of f(775, 527):
| Call | x | y | x mod y |
|---|---|---|---|
| 1 | 775 | 527 | 248 |
| 2 | 527 | 248 | 31 |
| 3 | 248 | 31 | 0 |
| 4 | 31 | 0 | — (return 31) |
The recursion terminates when y = 0, returning x = 31.
Why not others:
- (a) 0 — this would mean one number divides the other evenly at every step, which is not the case here.
- (c) 248 — this is an intermediate remainder (step 1), not the final GCD.
- (d) 527 — this is the original second argument, not the result of the algorithm.
Key rule: When you see f(x, y): if y = 0 return x, else return f(y, x mod y) — it is the Euclidean algorithm for GCD. Just trace the mod operations until y reaches 0.
AI-generated — may contain errors
The original exam layout is preserved in the image so diagrams, formulas, tables, and code remain accurate.
This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.