Consider the following ANSI C function: int SomeFunction (int x, int y) { if…
2021
Consider the following ANSI C function:
int SomeFunction (int x, int y)
{
if ((x==1) || (y==1)) return 1;
if (x==y) return x;
if (x > y) return SomeFunction(x-y, y);
if (y > x) return SomeFunction (x, y-x);
}
The value returned by SomeFunction(15, 255) is __________ .
Attempted by 146 students.
Show answer & explanation
Correct answer: 15
Key insight: the function implements the subtractive form of the Euclidean algorithm and therefore returns the greatest common divisor (GCD) of the two inputs.
If either argument is 1, the GCD is 1.
If the arguments are equal, that value is the GCD.
Otherwise the function subtracts the smaller from the larger and recurses, which is equivalent to the Euclidean algorithm.
Apply the function to (15, 255). Since 255 > 15, replace 255 with 255 - 15 = 240, giving (15, 240).
Repeat subtracting 15 from the second argument: (15, 225), (15, 210), … After 16 subtractions the pair becomes (15, 15).
When the arguments are equal (15, 15), the function returns 15, which is the GCD of 15 and 255.
Answer: 15
A video solution is available for this question — log in and enroll to watch it.