In this tutorial, we will learn about finding the Least Common Multiple (LCM) of two numbers in Python using recursion. The LCM of two numbers is the smallest number that is divisible by both numbers.
Recursion is a technique in computer programming where a function calls itself to solve a problem. In this case, we will use recursion to find the Greatest Common Divisor (GCD) of two numbers, which is a crucial step in finding the LCM.
Python Program to Find LCM of Two Numbers Using Recursion
Let’s start by defining the function for finding the GCD. The function is called find gcd and takes two parameters, a and b. The first line of the function checks if b is equal to zero. If b is equal to zero, the function returns a.
If b is not equal to zero, the function calls itself again with b and the remainder of a divided by b. This process continues until b becomes zero. At this point, the function returns the value of a, which is the GCD of the two numbers.
Next, we take two numbers as input from the user. These numbers are stored in the variables num1 and num2. The values are converted from strings to integers using the int() function.
We then call the find gcd function and store the result in a variable called gcd. The LCM is calculated by multiplying num1 and num2 and dividing the result by the gcd. The LCM is then printed using the print() function.
Here is the complete code:
# LCM of Two Numbers in Python Using Recursion
# Function definition
def findgcd(a, b):
if(b == 0):
return a;
else:
# Recursion takes place here
return findgcd(b, a % b)
# we are taking a number from user as input
# entered value will be converted to int from string
num1 = int(input("Enter the first number:"))
num2 = int(input("Enter the second number:"))
#function call
gcd = findgcd(num1, num2)
lcm = (num1 * num2) // gcd
#Print Result
print('LCM is:',lcm)
In this program, we discussed the LCM of two numbers in Python using Recursion. The LCM (Least Common Multiple) of two numbers is the smallest number that is a multiple of both numbers.
To understand the LCM, let’s take an example of two numbers, 5 and 10. The LCM of 5 and 10 is 10. To calculate the LCM, we need to use a mathematical concept called the GCD (Greatest Common Divisor).
The GCD of two numbers is the largest number that divides both the numbers. To find the LCM, we can use the formula: LCM = (num1 * num2) / GCD
Now let’s see this code in action by using examples 5 and 10:
Output:
Enter the first number:5
Enter the second number:10
LCM is: 10As you can see, the code has correctly calculated the LCM of 5 and 10, which is 10. The program takes two numbers as input from the user and finds the LCM of the two numbers.
The find gcd function calculates the GCD of two numbers using Recursion. If the second number is 0, the function returns the first number. If the second number is not 0, the function calculates the GCD by calling the function again with the second number and the remainder of dividing the first number by the second number.
The LCM is calculated using the formula LCM = (num1 * num2) / GCD, where num1 and num2 are the two numbers entered by the user, and GCD is the calculated GCD.
In conclusion, this code demonstrates how to find the LCM of two numbers in Python using Recursion. By using Recursion, we can easily find the LCM of two numbers, making this code an efficient solution for finding the LCM.
For More Python Programming Exercises and Solutions check out our Python Exercises and Solutions
About The Author
