C Program to Find GCD Using Recursion

You can find the GCD of two numbers in C using recursion by defining a function like int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a % b); } which calls itself until the remainder is zero.

Examples

Input48 18

OutputGCD of 48 and 18 is 6

Input100 25

OutputGCD of 100 and 25 is 25

Input7 3

OutputGCD of 7 and 3 is 1

How to Think About It

To find the GCD using recursion, think of the problem as repeatedly replacing the larger number by the remainder of dividing the larger by the smaller until the remainder is zero. When the remainder is zero, the smaller number at that point is the GCD. This uses the property that gcd(a, b) = gcd(b, a % b).

Algorithm

1

Get two numbers as input.

2

Check if the second number is zero.

3

If yes, return the first number as GCD.

4

If no, call the function again with the second number and the remainder of first number divided by second number.

5

Repeat until the second number becomes zero.

Code

c

#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

int main() {
    int x = 48, y = 18;
    printf("GCD of %d and %d is %d\n", x, y, gcd(x, y));
    return 0;
}

Output

GCD of 48 and 18 is 6

Dry Run

Let's trace gcd(48, 18) through the code

1

First call

gcd(48, 18): since 18 != 0, call gcd(18, 48 % 18) = gcd(18, 12)

2

Second call

gcd(18, 12): since 12 != 0, call gcd(12, 18 % 12) = gcd(12, 6)

3

Third call

gcd(12, 6): since 6 != 0, call gcd(6, 12 % 6) = gcd(6, 0)

4

Fourth call

gcd(6, 0): since 0 == 0, return 6

Call	a	b	a % b	Return value
1	48	18	12	calls gcd(18, 12)
2	18	12	6	calls gcd(12, 6)
3	12	6	0	calls gcd(6, 0)
4	6	0	-	returns 6

Why This Works

Step 1: Base Case

The recursion stops when the second number b becomes zero, returning the first number a as the GCD.

Step 2: Recursive Step

If b is not zero, the function calls itself with b and the remainder of a % b, reducing the problem size.

Step 3: Mathematical Property

This works because the GCD of two numbers also divides their difference, so gcd(a, b) = gcd(b, a % b).

Alternative Approaches

Iterative approach

c

#include <stdio.h>

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int x = 48, y = 18;
    printf("GCD of %d and %d is %d\n", x, y, gcd(x, y));
    return 0;
}

This uses a loop instead of recursion, which can be more efficient and avoids stack overflow for large inputs.

Using subtraction method

c

#include <stdio.h>

int gcd(int a, int b) {
    if (a == b)
        return a;
    if (a > b)
        return gcd(a - b, b);
    else
        return gcd(a, b - a);
}

int main() {
    int x = 48, y = 18;
    printf("GCD of %d and %d is %d\n", x, y, gcd(x, y));
    return 0;
}

This method uses repeated subtraction instead of modulo, but it is slower for large numbers.

Complexity: O(log(min(a, b))) time, O(log(min(a, b))) space

Time Complexity

Each recursive call reduces the problem size roughly by modulo operation, so the number of calls is proportional to the logarithm of the smaller input.

Space Complexity

The recursion stack grows with each call, so space used is proportional to the number of recursive calls, which is O(log(min(a, b))).

Which Approach is Fastest?

The iterative method is generally faster and uses less memory than recursion, but recursion is simpler to understand and implement.

Approach	Time	Space	Best For
Recursive (modulo)	O(log(min(a,b)))	O(log(min(a,b)))	Simple code, small inputs
Iterative (modulo)	O(log(min(a,b)))	O(1)	Large inputs, performance
Recursive (subtraction)	O(min(a,b))	O(min(a,b))	Educational, simple math