Lcm using recursion in python

Edit: I didn't read the recursive / one function bit in your question cause I'm dumb. Incorporated now.

The lcm isn't a * b / lcm[a, b], it's a * b / gcd[a, b] [greatest common divisor].

So the cleanest way to do this is:

def gcd[x, y]:
    while y:      
        x, y = y, x % y
    return x

def lcm[x, y]:
    return x * y / gcd[x, y]

If you are limited to recursion only [e.g. for an exam] then this doesn't have to be efficient, so you might as well just recursively count up until you find the lowest number that both x and y divide into:

def lcm[x, y, counter=1]:
    if [counter%x == 0 and counter%y == 0]:
        return counter
    return lcm[x, y, counter+1]

That just increases counter until counter%x == 0 and counter%y == 0 is true, which is the LCM. Don't try it on large numbers though, you'll just get a stack overflow.

LCM of a Number using Recursion

On this page we will learn to create a python program to find LCM of a Number using Recursion.

LCM – Lowest common multiple of two or more number. Is Smallest number that it is completely divisible by all the numbers for which we are finding LCM. 

Example :

• Input : first = 23, second = 69
• Output : HCF of 23 and 69 is 69
• Explanation : No other number less then 69 can be divide by both 23 and 69 completely. That’s why 69 is LCM of 23 & 69

Method 1 : Using Recursion

Algorithm

• Start by making a function and passing both number to it as a and b
• Return a multiplied divided by the value returned by another function which takes a and b
• If b is equals to zero return a
• Else return recursive call for the function with values b and remainder when a is divided by b respectively

Python Code

Run

def hcf[a, b]:
    if b == 0:
        return a
    else:
        return hcf[b, a % b]


def lcm[a, b]:
    return [a * b] // hcf[a, b]


first = 23
second = 69

print["Lcm of", first, "and", second, "is", lcm[first, second]]

Output :
Lcm of 23 and 69 is 69

Method 2: Using Loop

Algorithm

• Start by making a function and passing both number to it as a and b
• Return a multiplied by b divided by the value returned by another function which takes a and b
• If maximum between a & b is divided by minimum between a & b gives remainder zero return minimum between a & b
• Iterate using for loop between range one more then half of minimum between a & b to 0 in reverse order using variable i
• For each iteration check if  a divided by i and b divided by i both are equals to 0 then return i

Python Code

Run

def hcf[a, b]:
    if max[a, b] % min[a, b] == 0:
        return min[a, b]
    for i in range[1 + min[a, b] // 2, 0, -1]:
        if a % i == b % i == 0:
            return i


def lcm[a, b]:
    return [a * b] // hcf[a, b]


first = 23
second = 69

print['LCM of', first, 'and', second, 'is', lcm[first, second]]

Output :
Lcm of 23 and 69 is 69

For similar Questions click on the given button.

LCM of two numbers in python | 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.

Example:-
LCM of 3 and 5 is 15 because 15 is divisible by both 3 and 5.
LCM of 12 and 15 is 60 because 60 is divisible by both 12 and 15.

This is a normal method to find lcm of the two numbers in python. We will take two numbers while declaring the variables. Python program to find lcm of the two numbers using if-else statement and while loop.

# Python program to find the LCM of the two numbers

# take inputs
num1 = int[input['Enter first number: ']]
num2 = int[input['Enter second number: ']]

# choose the greater number
if [num1 > num2]:
    greater = num1
else:
    greater = num2

while[True]:
    # find LCM
    if[greater % num1 == 0 and greater % num2 == 0]:
        print['The LCM of',num1,'and',num2,'is',greater]
        break
    greater += 1

Output for the different input value:-

Enter first number: 2
Enter second number: 4
The LCM of 2 and 4 is 4

Enter first number: 3
Enter second number: 5
The LCM of 3 and 5 is 15

Enter first number: 20
Enter second number: 8
The LCM of 20 and 8 is 40

In each iteration, we check if both the numbers perfectly divide our number. If so, we store the number as L.C.M. and break from the loop. Otherwise, the number is incremented by 1 and the loop continues.

LCM Function in Python

We can also take the help of a function to find lcm of the two numbers in python. A function is a block of code that performs a specific task.

# Python program to find the LCM using function

def find_lcm[a, b]:   #user-defined function
   # choose the greater number
   if a > b:
       greater = a
   else:
       greater = b

   while[True]:
       # find LCM
       if[[greater % a == 0] and [greater % b == 0]]:
           lcm = greater
           break
       greater += 1
   return lcm

# take inputs
num1 = int[input['Enter first number: ']]
num2 = int[input['Enter second number: ']]

# calling function & display result
print['The LCM of',num1,'and',num2,'is',find_lcm[num1, num2]]

Output:-

Enter first number: 50
Enter second number: 40
The LCM of 50 and 40 is 200

Program using GCD

The above program methods are slower to run. We can make it more efficient and faster by using the fact that the product of two numbers a and b is equal to the product of HCF[a,b] and LCM[a,b].

a*b = HCF[a, b] * LCM[a, b]

The HCF [ highest common factor ] is also referred also as GCD [ Greatest Common Measure ], Using this formula we can find GCD and LCM at a time. We need to find either GCD and LCM and then apply this formula.

In the below program to find the LCM of two numbers in python; First, we find the HCF then using the formula LCM will be calculated. The Formula used for this purpose is:-

LCM[a, b] = [a*b] / HCF[a, b]

# Python program to find the LCM using GCD

# This function find GCD 
def find_gcd[a, b]:
    while[b]:
        a, b = b, a % b
    return a

# This function find LCM
def find_lcm[a, b]:
    lcm = [a*b]//find_gcd[a,b]
    return lcm

# take inputs
num1 = int[input['Enter first number: ']]
num2 = int[input['Enter second number: ']]

# calling function & display result
print['The LCM of',num1,'and',num2,'is',find_lcm[num1, num2]]

Output:-

Enter first number: 10
Enter second number: 25
The LCM of 10 and 25 is 50

LCM of Two Numbers in Python using Recursion

We can also use the recursion technique to find the lcm of two numbers. A technique of defining the method/function that contains a call to itself is called recursion. The recursive function/method 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.

# Python program to find the LCM using recursion

# This recursive function find GCD 
def find_gcd[a, b]:
    if[b == 0]:
        return a
    else:
        return find_gcd[b, a%b]

# take inputs
num1 = int[input['Enter first number: ']]
num2 = int[input['Enter second number: ']]

# find LCM
lcm = [num1 * num2] // find_gcd[num1, num2]

# display result
print['The LCM of',num1,'and',num2,'is',lcm]

Output:-

Enter first number: 9
Enter second number: 31
The LCM of 9 and 31 is 279

Also See:- Find Factorial of a Number in Python

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!

How do you find LCM with recursion?

How do you do LCM in python?

How do you find the LCM in a while loop in python?

How do you print HCF and LCM in python?