Python Program to Find the LCM of Two Numbers Using Recursion

Practice Java programming from home without using any fancy software just by tapping on this Simple Java Programs for Beginners tutorial.

Recursion:

Recursion is a functional technique to problem-solving that involves breaking an issue down into a series of small subproblems with an identical pattern and solving them sequentially by calling one subproblem within another. Recursion is carried out by defining a function capable of solving one subproblem at a time. It calls itself but solves another subproblem somewhere inside that method. As a result, the call to itself continues until some limiting requirements are met.

The main program’s first call to a recursive function will be returned only after all sub calls have completed. As a result, Python keeps the results of all subproblems in temporary memory, does some arithmetic operations (if necessary), and releases the memory at the end of the recursion.

The smallest positive number that is divisible by both a and b is the least or lowest common multiple (LCM) of two numbers a and b. In this article, we’ll look at how to use recursion to find the LCM of two numbers.

Examples:

Example1:

Input:

given first number = 10
given second number = 16

Output:

The value of lcm of the given two numbers 10 16  =  80

Example2:

Input:

given first number = 10
given second number = 16

Output:

The value of lcm of the given two numbers 5 17  =  85

Program to Find the LCM of Two Numbers Using Recursion in Python

There are several ways to calculate the lcm of the given two numbers using recursion some of them are:

Using Recursion (Static Input)
Using Recursion (User Input separated by space)
Using Recursion (User Input separated by newline)

Method #1:Using Recursion (Static Input)

Approach:

Give two numbers as static input and store them in two variables.
Pass the given two numbers as arguments to the recursive function which calculates the lcm of the given two numbers.
Set the multiple variable to the highest value between the given two numbers.
Check to see if the multiple variable divides both given numbers perfectly.
If it does, the process is terminated and the multiple variable is returned as the LCM.
If the multiple does not divide both given numbers perfectly, then it is increased by the maximum value among both given numbers using the max() function.
The recursive function returns the multiple variable which is the result(lcm of the given two numbers)
Print the LCM of the given two numbers.
The Exit of the Program.

Below is the implementation:

# function which accepts the given two numbers as arguments
# and return the lcm of the given two numbers.


def lcmRecursion(numb1, numb2):
    # Set the multiple variable to the highest value between the given two numbers.
    lcmRecursion.multiple = lcmRecursion.multiple+numb2
    # Check to see if the multiple variable  divides both given numbers perfectly.
    if((lcmRecursion.multiple % numb1 == 0) and (lcmRecursion.multiple % numb2 == 0)):
      # If it does, the process is terminated and the multiple variable is returned as the LCM.
        return lcmRecursion.multiple
    else:
      # If the multiple does not divide both given numbers perfectly, then it is increased by the maximum value
      # among both given numbers using the max() function.
        lcmRecursion(numb1, numb2)
    # The recursive function returns the multiple variable
    # which is the result(lcm of the given two numbers)
    return lcmRecursion.multiple


# set multiplee variable value to 0
lcmRecursion.multiple = 0
# Give two numbers as static input and store them in two variables.
numbe1 = 10
numbe2 = 16
# if the first number is greater than second number then swap the arguments
if(numbe1 > numbe2):
    LcmVal = lcmRecursion(numbe2, numbe1)
# else pass the original numbers as arguments
else:
    LcmVal = lcmRecursion(numbe1, numbe2)
print('The value of lcm of the given two numbers', numbe1, numbe2, ' = ', LcmVal)

Output:

The value of lcm of the given two numbers 10 16  =  80

Explanation:

The two numbers are given as static input.
The multiple variable is set to the highest value between the given two numbers.
The multiple variable is tested to see if it divides the given two numbers perfectly.
If so, the procedure is terminated and the multiple is returned as the LCM.
If the multiple variable does not divide the given two numbers perfectly, the multiple variable is returned by the maximum value among both given numbers.
The variable with multiple values is returned, and the LCM of the two variables is printed.

Method #2:Using Recursion (User Input separated by space)

Approach:

Scan the given two numbers as user input using a map, int, and split() functions and store them in two variables.
Pass the given two numbers as arguments to the recursive function which calculates the lcm of the given two numbers.
Set the multiple variable to the highest value between the given two numbers.
Check to see if the multiple variable divides both given numbers perfectly.
If it does, the process is terminated and the multiple variable is returned as the LCM.
If the multiple does not divide both given numbers perfectly, then it is increased by the maximum value among both given numbers using the max() function.
The recursive function returns the multiple variable which is the result(lcm of the given two numbers)
Print the LCM of the given two numbers.
The Exit of the Program.

Below is the implementation:

# function which accepts the given two numbers as arguments
# and return the lcm of the given two numbers.


def lcmRecursion(numb1, numb2):
    # Set the multiple variable to the highest value between the given two numbers.
    lcmRecursion.multiple = lcmRecursion.multiple+numb2
    # Check to see if the multiple variable  divides both given numbers perfectly.
    if((lcmRecursion.multiple % numb1 == 0) and (lcmRecursion.multiple % numb2 == 0)):
      # If it does, the process is terminated and the multiple variable is returned as the LCM.
        return lcmRecursion.multiple
    else:
      # If the multiple does not divide both given numbers perfectly, then it is increased by the maximum value
      # among both given numbers using the max() function.
        lcmRecursion(numb1, numb2)
    # The recursive function returns the multiple variable
    # which is the result(lcm of the given two numbers)
    return lcmRecursion.multiple


# set multiplee variable value to 0
lcmRecursion.multiple = 0
# Scan the given two numbers as user input using a map,
# int, and split() functions and store them in two variables.
numbe1, numbe2 = map(int, input(
    'Enter two random numbers separated by space =').split())
# if the first number is greater than second number then swap the arguments
if(numbe1 > numbe2):
    LcmVal = lcmRecursion(numbe2, numbe1)
# else pass the original numbers as arguments
else:
    LcmVal = lcmRecursion(numbe1, numbe2)
print('The value of lcm of the given two numbers', numbe1, numbe2, ' = ', LcmVal)

Output:

Enter two random numbers separated by space =5 17
The value of lcm of the given two numbers 5 17 = 85

Explanation:

Here the map function converts the given two numbers from string to integer data type and the split() function
splits the given two numbers by space.

Method #3:Using Recursion (User Input separated by newline)

Approach:

Scan the first number as user input using the int(input()) function and store it in a variable.
Scan the second number as user input using the int(input()) function and store it in another variable.
Here int() is used to convert the given number to integer datatype.
Pass the given two numbers as arguments to the recursive function which calculates the lcm of the given two numbers.
Set the multiple variable to the highest value between the given two numbers.
Check to see if the multiple variable divides both given numbers perfectly.
If it does, the process is terminated and the multiple variable is returned as the LCM.
If the multiple does not divide both given numbers perfectly, then it is increased by the maximum value among both given numbers using the max() function.
The recursive function returns the multiple variable which is the result(lcm of the given two numbers)
Print the LCM of the given two numbers.
The Exit of the Program.

Below is the implementation:

# function which accepts the given two numbers as arguments
# and return the lcm of the given two numbers.


def lcmRecursion(numb1, numb2):
    # Set the multiple variable to the highest value between the given two numbers.
    lcmRecursion.multiple = lcmRecursion.multiple+numb2
    # Check to see if the multiple variable  divides both given numbers perfectly.
    if((lcmRecursion.multiple % numb1 == 0) and (lcmRecursion.multiple % numb2 == 0)):
      # If it does, the process is terminated and the multiple variable is returned as the LCM.
        return lcmRecursion.multiple
    else:
      # If the multiple does not divide both given numbers perfectly, then it is increased by the maximum value
      # among both given numbers using the max() function.
        lcmRecursion(numb1, numb2)
    # The recursive function returns the multiple variable
    # which is the result(lcm of the given two numbers)
    return lcmRecursion.multiple


# set multiplee variable value to 0
lcmRecursion.multiple = 0
# Scan the first number as user input using the int(input())
# function and store it in a  variable.
numbe1 = int(input('Enter some random number = '))
# Scan the second number as user input using the int(input())
# function and store it in another variable.
# Here int() is used to convert the given number to integer datatype.
numbe2=int(input('Enter some random number = '))
# if the first number is greater than second number then swap the arguments
if(numbe1 > numbe2):
    LcmVal=lcmRecursion(numbe2, numbe1)
# else pass the original numbers as arguments
else:
    LcmVal=lcmRecursion(numbe1, numbe2)
print('The value of lcm of the given two numbers', numbe1, numbe2, ' = ', LcmVal)

Output:

Enter some random number = 9
Enter some random number = 3
The value of lcm of the given two numbers 9 3 = 9

Related Programs: