How to Find LCM Using Recursion Technique

Least or lowest common multiple (LCM) of two integers a and b is the smallest positive number that is divisible by both a and b. Here we will learn how to find the LCM of the two numbers using the recursion technique.

A function that contains a call to itself is called the recursive function. A technique of defining the recursive function is called recursion. The recursive function allows us to divide the complex problem into identical single simple cases that can handle easily. This is also a well-known computer programming technique: divide and conquer.

A recursive function must have at least one exit condition that can satisfy. Otherwise, the recursive function will call itself repeatedly until the runtime stack overflows. To prevent infinite recursion generally if-else (or similar approach) can be used where one branch makes the recursive call and the other doesn’t.

Recursive function to find LCM of two numbers

int lcm(int a, int b)
{
  // static variable
  static int common = 0;

  // add largest number
  common += b; 

  // base case
  if(common%a == 0) return common; 

  // general case
  else return lcm(a, b); 
}

The lcm() recursive function takes two integers as an argument. Take a static variable common and initialize it with zero, then update with one of the numbers. Here, we update the common variable with b, so variable common will always divisible by the variable b. Hence we need to check only with variable a i.e (common%a == 0).

Note:- Since we are adding largest number to the common variable, therefore b variable must hold the largest number. While calling lcm() we must pass smallest number as a, and greatest number as b.

int num1, num2;
// read num1 and num2
if(num1 < num2) result = lcm(num1, num2);
else result = lcm(num2, num1);

Why we should add the largest number while finding LCM using recursion technique?

If we add the largest number then the number of the recursive call will be minimum, but if we add smallest number then number of the recursive call will be more than from the previous case. We know that less number of recursive call gives high performance.

Take the example of numbers 3 and 7. If we add largest number 7 to the sum variable then,
0+7 = 7 (call from main function), 7%3 != 0
7+7 = 14 (first recursive call), 14%3 != 0
14+7 = 21 (second recursive call)
21 is divisible by both 3 and 7
Hence, there will be only 2 recursive calls.

Similarly, if we take smallest number (3) then,
0+3 = 3 , 3%7 != 0
3+3 = 6 , 6%7 != 0
6+3 = 9 , 9%7 != 0
9+3 = 12 , 12%7 != 0
12+3 = 15 , 15%7 != 0
15+3 = 18 , 18%7 != 0
18+3 = 21
21 is divisible by both 3 and 7
Hence, there will be 6 recursive calls.

It was a very small example, for the large numbers there will be a huge difference. Now let us develop a C program to find LCM using recursion technique.

C program to find LCM using recursion

#include<stdio.h>
int lcm(int a, int b)
{
  static int common = 0;

  // increase common by adding max value
  common += b;

  if(common%a == 0) return common; //base case
  else return lcm(a, b); // general case
}

int main()
{
   int num1, num2, result;

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

   if(num1 < num2) result = lcm(num1, num2);
   else result = lcm(num2, num1);

   printf("LCM = %d", result);

   return 0;
}

Output:-

Enter two integers: 12 15
LCM = 60

Enter two integers: 16 18
LCM = 144

In this C program to find LCM using recursion, we take two integers as input from the user. Later we use the if-else statement. In the recursive function LCM, we add the b variable to the sum variable. We should pass the largest number as the second argument. To find the largest number, we used the if-else statement.

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!

Leave a Comment

Your email address will not be published. Required fields are marked *