Question 6.
Cognizant technical mcq question, verified with a worked answer. Free to practise - no sign-up.
GCD of two numbers. #include <stdio.h>
// Recursive function to return gcd of a and b int gcd(int a, int b)
{
// Everything divides 0 if (a == 0 || b == 0)
return 0;
// base case if (a == b)
return a;
// a is greater if (a > b)
return gcd(a-b, b);
return gcd(a, b-a);
}
// Driver program to test above function int main()
{
int a = 98, b = 56;
printf("GCD of %d and %d is %d ", a, b, gcd(a, b)); return 0;
}
Or
class Test
{
// Recursive function to return gcd of a and
Show answer & explanation
The function uses the subtraction-based Euclidean algorithm. Starting with gcd(98, 56): it recursively subtracts the smaller from the larger until both become equal. The GCD of 98 and 56 is 14, which is the largest number that divides both 98 (98 = 14 × 7) and 56 (56 = 14 × 4). The base case a == 0 || b == 0 returning 0 is actually a logic flaw in this implementation—it should return the non-zero value—but since the recursion terminates when a == b (both equal to 14), this flaw is never reached.
Step-by-step Derivation:
Trace the recursion:
- gcd(98, 56): 98 > 56 → gcd(98-56, 56) = gcd(42, 56)
- gcd(42, 56): 42 < 56 → gcd(42, 56-42) = gcd(42, 14)
- gcd(42, 14): 42 > 14 → gcd(42-14, 14) = gcd(28, 14)
- gcd(28, 14): 28 > 14 → gcd(28-14, 14) = gcd(14, 14)
- gcd(14, 14): a == b → return 14
Result: 14