GCD and LCM Using Recursion in C – Euclidean Algorithm

This C program finds GCD and LCM using recursion with the Euclidean algorithm. The GCD (Greatest Common Divisor) is the largest number that divides both inputs with no remainder. The LCM (Least Common Multiple) is the smallest number divisible by both. Once the GCD is known, the LCM follows from a simple identity: GCD(a, b) × LCM(a, b) = a × b.

For the iterative (loop-based) version, see GCD and LCM Without Recursion.

The Recursive Euclidean Algorithm

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

Trace GCD(8, 12):

GCD(8, 12) = 4. LCM = 8 / 4 × 12 = 24.

Trace GCD(15, 25):

GCD(15, 25) = 5. LCM = 15 / 5 × 25 = 75.

C Program — GCD and LCM Using Recursion

/* GCD and LCM using recursion in C
 * Compile: gcc -ansi -Wall -Wextra gcd_recursive.c -o gcd_recursive */
#include <stdio.h>

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 positive integers: ");
    scanf("%d %d", &num1, &num2);

    if (num1 <= 0 || num2 <= 0) {
        printf("Please enter positive integers.\n");
        return 1;
    }

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

    printf("GCD of %d and %d = %d\n", num1, num2, g);
    printf("LCM of %d and %d = %d\n", num1, num2, lcm);

    return 0;
}

How to Compile and Run

gcc -ansi -Wall -Wextra gcd_recursive.c -o gcd_recursive
./gcd_recursive

Sample Input and Output

Enter two positive integers: 8 12
GCD of 8 and 12 = 4
LCM of 8 and 12 = 24

Enter two positive integers: 15 25
GCD of 15 and 25 = 5
LCM of 15 and 25 = 75

Enter two positive integers: 7 13
GCD of 7 and 13 = 1
LCM of 7 and 13 = 91

(Two coprime numbers have GCD = 1 and LCM = their product.)

Enter two positive integers: 100 75
GCD of 100 and 75 = 25
LCM of 100 and 75 = 300

Code Explanation

• Base case: if (b == 0) return a — when b reaches 0, a holds the GCD. Every sequence of remainders eventually reaches 0 because the remainder is always strictly smaller than the divisor.
• Recursive step: return gcd(b, a % b) — the remainder a % b is smaller than b. So each recursive call shrinks the second argument. The sequence is guaranteed to terminate.
• Self-correcting for order — gcd(8, 12) makes a first call to gcd(12, 8) because 8 % 12 = 8. The algorithm works correctly regardless of which number is larger — no sorting needed.
• lcm = (num1 / g) * num2 — divides before multiplying to reduce overflow risk. num1 * num2 could overflow int for large inputs; dividing num1 by g first gives a smaller intermediate value.
• Why a / gcd × b never loses precision — since gcd divides num1 exactly, num1 / gcd is always an integer, so no fractional part is discarded.

Recursion vs Iteration for GCD

For GCD, the recursion depth is bounded by the Fibonacci sequence — the worst case is consecutive Fibonacci numbers (e.g., GCD(55, 34) takes 9 calls). For 32-bit integers the maximum depth is about 45 calls, which is never a stack concern.

What This Program Teaches

• Direct translation of a mathematical definition to code — the recursive gcd() is almost a word-for-word transcription of the Euclidean algorithm’s definition. This is recursion at its clearest.
• The base case and recursive case pattern — every correct recursive function has a base case that stops the recursion and a recursive case that moves toward it. Identify both before writing any recursive function.
• Overflow-safe compound formulas — dividing before multiplying is a general technique. Whenever a formula involves a product that could overflow, look for a way to cancel factors first.
• GCD as a foundation — GCD is used in fraction reduction (a/b → (a/gcd)/(b/gcd)), modular arithmetic, prime factorization, and coprimality tests. Mastering the Euclidean algorithm unlocks a wide range of number theory applications.

Related Programs

• GCD and LCM Without Recursion (Iterative)
• Factorial Using Recursion in C
• Fibonacci Using Recursion in C
• Perfect Number in C
• Factors of a Number in C

Recommended book:
The C Programming Language — Kernighan & Ritchie (India) |
(US)
 | 
C Programming: A Modern Approach — K.N. King (India) |
(US)

Practice what you learned: C Aptitude Questions — or try our C Programming Quiz App on Android.