QUESTION 41 · Recursion

State the base case in recursive Euclid’s GCD algorithm.

2 marks

Answer

When b is zero, return a.

For b non-zero, use gcd(b, a % b).
Use supported non-negative inputs and reject the pair 0, 0 in this example.

Write a recursive C program to find the greatest common divisor using Euclid’s method.

5 marks

Answer in brief

Euclid’s method finds the greatest common divisor by repeatedly replacing a pair with the second value and the remainder.

Recursive rule

gcd(a, b) = a                 when b == 0
gcd(a, b) = gcd(b, a % b)     otherwise

Algorithm

Read two non-negative integers within the supported range. Reject the pair 0, 0.
If b is zero, return a.
Otherwise, call gcd with b and a % b.
Return the smaller call’s result and display it.

Worked trace

For 48 and 18, the first remainder is 12, so the next pair is (18, 12). The next remainder is 6, giving (12, 6). The next remainder is zero, giving (6, 0). The base case returns 6. Earlier calls return the same value, so the greatest common divisor is 6.

Why the rule works

Replacing a by a - q × b does not change the common divisors of a and b. The remainder a % b is exactly that difference for the integer quotient q. Thus the common divisors remain the same while the values become smaller. For positive b, the non-negative remainder is less than b, ensuring progress.

Boundary cases

gcd(a, 0) returns a for positive a; gcd(0, b) returns b for positive b. This program rejects (0, 0) rather than assigning it an elementary greatest-positive-divisor result.

Complexity

For positive inputs, Euclid’s algorithm uses O(log min(a, b)) remainder steps; more precisely the boundary cases can be expressed using 1 + min(a, b). Each one or two steps substantially reduces the smaller positive value. Recursive auxiliary space follows the number of active calls. Zero-input cases finish in constant work. This analysis treats fixed-width arithmetic operations as constant time.

C program and output

Download .c Open compiler

/* CodeBhavya | PPS AR25 | Learning example */
#include <stdio.h>
unsigned int gcd(unsigned int a, unsigned int b)
{
    if (b == 0U) { return a; }
    return gcd(b, a % b);
}
int main(void)
{
    int a, b;
    if (scanf("%d%d", &a, &b) != 2 || a < 0 || b < 0 ||
        a > 10000 || b > 10000 || (a == 0 && b == 0)) {
        puts("Unsupported input"); return 1;
    }
    printf("GCD = %u\n", gcd((unsigned int)a, (unsigned int)b));
    return 0;
}

Sample input and output

Input

48 18

Output

GCD = 6