C Program to Find LCM and GCD Using Recursion

1. Introduction

LCM (Least Common Multiple) and GCD (Greatest Common Divisor) are fundamental mathematical operations often used in number theory. In this post, we'll explore how to compute the LCM and GCD of two numbers using recursion in the C programming language.

2. Program Overview

The program will:

1. Define recursive functions for calculating the GCD.

2. Use the relationship between LCM and GCD to compute LCM: lcm(a,b) = (a * b) / gcd(a,b).

3. Get two numbers from the user.

4. Calculate and display the GCD and LCM of the entered numbers.

3. Code Program

#include <stdio.h>

// Recursive function to return GCD of a and b
int gcd(int a, int b) {
    if (b == 0)  // Base case
        return a;
    return gcd(b, a % b);  // Recursive case
}

// Function to return LCM of two numbers
int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

int main() {
    int num1, num2;

    // Getting numbers from the user
    printf("Enter two integers: ");
    scanf("%d%d", &num1, &num2);

    // Displaying the results
    printf("GCD of %d and %d is %d\n", num1, num2, gcd(num1, num2));
    printf("LCM of %d and %d is %d\n", num1, num2, lcm(num1, num2));

    return 0;
}

Output:

For input numbers 12 and 15, the program would output:
GCD of 12 and 15 is 3
LCM of 12 and 15 is 60

4. Step By Step Explanation

1. The program begins with the definition of the gcd function. This function uses Euclid's algorithm to find the GCD of two numbers:

- If b is 0, return a (base case).- Otherwise, recursively call the gcd function with arguments b and a % b.

2. The lcm function calculates the LCM using the relationship between LCM and GCD: lcm(a,b) = (a * b) / gcd(a,b). This formula takes advantage of the fact that the product of two numbers is equal to the product of their LCM and GCD.

3. In the main function, the program gets two integer inputs from the user.

4. The GCD and LCM of these numbers are then calculated using the gcd and lcm functions respectively.

5. Finally, the program displays the computed GCD and LCM of the input numbers.