C Program to find GCD and LCM using Recursion

This C program finds the GCD (Greatest Common Divisor) and LCM (Least Common Multiple) of two numbers using recursion. Recursion is a technique where a function calls itself to solve a smaller version of the same problem. The GCD is computed with the classic recursive Euclidean algorithm, and the LCM is then derived from it using a simple mathematical identity.

The Key Idea

For any two positive integers, GCD(a, b) × LCM(a, b) = a × b. So once we know the GCD, the LCM is just:

LCM = (a / GCD) × b

The recursive Euclidean rule for GCD is: GCD(a, b) = GCD(b, a % b), stopping when b becomes 0.

The Program

#include <stdio.h>

/* Recursive Euclidean algorithm for GCD. */
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int main(void)
{
    int num1, num2, g, lcm;

    printf("Enter two numbers : ");
    scanf("%d %d", &num1, &num2);

    g = gcd(num1, num2);
    lcm = (num1 / g) * num2;   /* divide first to avoid overflow */

    printf("GCD of %d and %d is : %d\n", num1, num2, g);
    printf("LCM of %d and %d is : %d\n", num1, num2, lcm);
    return 0;
}

How the Program Works

• gcd() calls itself with (b, a % b) each time. The remainder shrinks on every call until b is 0, at which point a holds the GCD — this is the recursive base case.
• The LCM uses the identity above. We divide num1 / g before multiplying by num2 to reduce the risk of integer overflow on large inputs.
• This is far cleaner than the original textbook version, which counted upwards with a static variable inside the recursion — correct but confusing and slow.

Sample Output

Enter two numbers : 8 12
GCD of 8 and 12 is : 4
LCM of 8 and 12 is : 24

For a clear explanation of recursion and the Euclidean algorithm, The C Programming Language by Kernighan and Ritchie is the classic reference — find it on Amazon.

This post contains affiliate links. If you buy through them, we may earn a small commission at no extra cost to you.

Related C Programs

• GCD and LCM Without Recursion (Iterative)
• Complete List of C Programs

Try it instantly in one of the best online C compilers, or set up a local toolchain with our complete C development environment guide.