Python Programs

Share with a Friend

Python Programs - Recursion Functions

Recursive function to find LCM - Python Program

Example 1 :

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

def lcm(a, b):
    """Find LCM using recursion."""
    return abs(a*b) // gcd(a, b)

print(lcm(12, 18))

 
OUTPUT  :
36 

Example 2 : Advanced Program

def recursive_gcd(a, b):
    """
    Recursively calculates the Greatest Common Divisor (GCD) of two numbers
    using the Euclidean algorithm.
    """
    if b == 0:
        return a
    else:
        return recursive_gcd(b, a % b)

def recursive_lcm(a, b):
    """
    Calculates the Least Common Multiple (LCM) of two numbers recursively
    by utilizing the recursive_gcd function.
    """
    if a == 0 or b == 0:
        return 0  # LCM is 0 if either number is 0
    else:
        return abs(a * b) // recursive_gcd(a, b)

# Example Usage
num1 = int(input("Enter first number  : "))
num2 = int(input("Enter second number  : "))

lcm_result = recursive_lcm(num1, num2)
print(f"The LCM of {num1} and {num2} is: {lcm_result}")

 
OUTPUT  :
Enter first number  : 12
Enter second number  : 18
The LCM of 12 and 18 is: 36

Explanation:

recursive_gcd(a, b) function:

• This function implements the Euclidean algorithm recursively to find the GCD.
• Base Case:If b is 0, then a is the GCD, and the function returns a.
• Recursive Step:Otherwise, it recursively calls recursive_gcd with b and the remainder of a divided by b (a % b). This process continues until the remainder becomes 0.

recursive_lcm(a, b) function:

• This function calculates the LCM using the relationship between LCM and GCD.
• Base Case:If either a or b is 0, the LCM is 0, and the function returns 0.
• Calculation:It uses the recursive_gcd function to find the GCD of a and b. Then, it applies the formula LCM(a, b) = (|a * b|) / GCD(a, b) to compute the LCM. The abs() function is used to handle potential negative inputs, ensuring a positive LCM result.