Consider the recursive Euclidean algorithm implemented as follows: What is the return value...
Accenture technical mcq question, verified with a worked answer. Free to practise - no sign-up.
Consider the recursive Euclidean algorithm implemented as follows:
function f(a, b) {
if (b == 0) {
return a;
} else {
return f(b, a % b);
}
}
What is the return value of f(10, 2)?
Show answer & explanation
Answer: A. 2
The function implements the Euclidean GCD algorithm. Tracing f(10, 2): since b ≠ 0, we call f(2, 10 % 2) = f(2, 0). Now b = 0, so we return a = 2. The GCD of 10 and 2 is indeed 2.
Step-by-step Derivation:
Step-by-step execution:
- f(10, 2): b = 2 ≠ 0, so return f(2, 10 % 2)
- 10 % 2 = 0
- Call f(2, 0)
- f(2, 0): b = 0, so return a = 2
- Result: 2
Verification: GCD(10, 2) = 2, since 2 divides 10 evenly (10 = 2 × 5).