Consider the recursive function for two positive integers a and b: What mathematical...
Accenture technical mcq question, verified with a worked answer. Free to practise - no sign-up.
Consider the recursive function for two positive integers $a$ and $b$:
function gcd(a, b) {
if (b === 0)
return a;
else
return gcd(b, a % b);
}
What mathematical quantity does this function calculate?
Show answer & explanation
This is the Euclidean algorithm, which computes the GCD of two numbers by recursively replacing the pair (a, b) with (b, a % b) until b becomes 0, at which point a is the GCD. The base case returns a when b = 0, confirming this is the standard GCD algorithm. Options B, C, and D are mathematically unrelated to this recursive structure.
Step-by-step Derivation:
Trace execution with example gcd(48, 18):
- gcd(48, 18): b ≠ 0, so call gcd(18, 48 % 18) = gcd(18, 12)
- gcd(18, 12): b ≠ 0, so call gcd(12, 18 % 12) = gcd(12, 6)
- gcd(12, 6): b ≠ 0, so call gcd(6, 12 % 6) = gcd(6, 0)
- gcd(6, 0): b = 0, return a = 6
Result: 6 is indeed the GCD of 48 and 18 (48 = 6×8, 18 = 6×3). The algorithm repeatedly applies the modulo operation, which is the hallmark of the Euclidean algorithm for GCD.