C Program to find LCM of two numbers using Recursion

0 0 2 minutes read

Given two integers N and M, the task is to find their LCM using recursion.

Examples:

Input: N = 2, M = 4
Output: 4
Explanation: LCM of 2, 4 is 4.

Input: N = 3, M = 5
Output: 15
Explanation: LCM of 3, 5 is 15.

Approach: The idea is to use the basic elementary method of finding LCM of two numbers. Follow the steps below to solve the problem:

Define a recursive function LCM() with 3 integer parameters N, M, and K to find LCM of N and M.
The following base conditions need to be considered:
- If N or M is equal to 1, return N * M.
- If N is equal to M, return N.
If K < min(N, M):
- If K divides both N and M, return K * LCM(N/K, M/K, 2).
- Otherwise, increment K by 1 and return LCM(N, M, K+1).
Otherwise, return the product of N and M.
Finally, print the result of the recursive function as the required LCM.

Below is the implementation of the above approach:

C

// C program for the above approach 
  
#include <stdio.h> 
  
// Function to return the 
// minimum of two numbers 
int Min(int Num1, int Num2) 
{ 
    return Num1 >= Num2 
               ? Num2 
               : Num1; 
} 
  
// Utility function to calculate LCM 
// of two numbers using recursion 
int LCMUtil(int Num1, int Num2, int K) 
{ 
    // If either of the two numbers 
    // is 1, return their product 
    if (Num1 == 1 || Num2 == 1) 
        return Num1 * Num2; 
  
    // If both the numbers are equal 
    if (Num1 == Num2) 
        return Num1; 
  
    // If K is smaller than the 
    // minimum of the two numbers 
    if (K <= Min(Num1, Num2)) { 
  
        // Checks if both numbers are 
        // divisible by K or not 
        if (Num1 % K == 0 && Num2 % K == 0) { 
  
            // Recursively call LCM() function 
            return K * LCMUtil( 
                           Num1 / K, Num2 / K, 2); 
        } 
  
        // Otherwise 
        else
            return LCMUtil(Num1, Num2, K + 1); 
    } 
  
    // If K exceeds minimum 
    else
        return Num1 * Num2; 
} 
  
// Function to calculate LCM 
// of two numbers 
void LCM(int N, int M) 
{ 
    // Stores LCM of two number 
    int lcm = LCMUtil(N, M, 2); 
  
    // Print LCM 
    printf("%d", lcm); 
} 
  
// Driver Code 
int main() 
{ 
    // Given N & M 
    int N = 2, M = 4; 
  
    // Function Call 
    LCM(N, M); 
  
    return 0; 
}

Output:

Time Complexity: O(max(N, M))
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!