Recursive LCM Calculation in C

Introduction

In this lab, we will write a C program to find the LCM (Least Common Multiple) of two numbers using recursion. LCM is the smallest positive integer that is divisible by both the numbers without leaving any remainder.

Skills Graph

Understand the concept of LCM

Before we begin with the programming, let's understand the concept of LCM. The LCM of two integers is the smallest positive integer that is a multiple of both the numbers. To find the LCM of two numbers, we can use the following formula:

LCM = (number1 * number2) / GCD

Where number1 and number2 are the two numbers for which we need to find the LCM and GCD is the Greatest Common Divisor of the two numbers.

Create a new C file

Let's create a new C file named main.c in the ~/project/ directory where we will write our program.

Write the code

Copy and paste the following code into the main.c file.

#include<stdio.h>

int find_lcm(int, int); // function prototype declaration

int main()
{
    int a, b, lcm;
    printf("Enter two integers to find LCM:\n");
    scanf("%d %d", &a, &b);
    lcm = find_lcm(a, b); // function call
    printf("LCM of %d and %d is %d.\n", a, b, lcm);

    return 0;
}

int find_lcm(int a, int b) // function definition
{
    static int temp = 1;
    if(temp % a == 0 && temp % b == 0)
        return temp;
    else
    {
        temp++;
        find_lcm(a, b);
        return temp;
    }
}

Compile and run the program

Save the main.c file and compile the program using the following command in the terminal:

gcc main.c -o main

Run the program using the following command:

./main

Enter two integers when prompted and the program will display the LCM of the two numbers.

Understand the code

Let's understand the code we just wrote.

• We first include the standard input and output library in our program using #include<stdio.h>.
• We declare the find_lcm function prototype which we will define later in our program. This is necessary because we are calling the find_lcm function in our main function before its actual definition.
• In the main function, we declare three integer variables a, b, and lcm.
• We prompt the user to enter two integers using printf and accept input using scanf.
• We then call the find_lcm function and pass a and b as its arguments.
• The find_lcm function takes two integer arguments a and b and returns the LCM of the two numbers using recursion.
• We initialize a static variable temp to 1, which will hold the current value that we are checking for a multiple.
• In each recursion, we check whether temp is a multiple of both a and b.
• If it is a multiple, we return temp as the LCM.
• If it is not a multiple, we increment temp and call the find_lcm function recursively until we find the LCM.

Test the program

Test the program with different input values and verify that it produces the correct LCM output.

Full code

Here is the full code for the C Program to find LCM of two Numbers using Recursion:

#include<stdio.h>

int find_lcm(int, int); // function prototype declaration

int main()
{
    int a, b, lcm;
    printf("Enter two integers to find LCM:\n");
    scanf("%d %d", &a, &b);
    lcm = find_lcm(a, b); // function call
    printf("LCM of %d and %d is %d.\n", a, b, lcm);

    return 0;
}

int find_lcm(int a, int b) // function definition
{
    static int temp = 1;
    if(temp % a == 0 && temp % b == 0)
        return temp;
    else
    {
        temp++;
        find_lcm(a, b);
        return temp;
    }
}

Summary

In this lab, we learned how to write a C program to find the LCM of two numbers using recursion. We used a recursive function to find the LCM and explained each step of the program in detail. We also learned how to compile and run a C program using the terminal.