Python Program to Find the LCM of Two Numbers using Recursion

1. Introduction

The LCM of two numbers is the smallest non-zero integer that is a multiple of both numbers. It can be found using the GCD (Greatest Common Divisor) of these numbers with the formula LCM(a, b) = |a * b| / GCD(a, b). The GCD can be calculated recursively using Euclid's algorithm.

2. Program Steps

1. Define a recursive function to find the GCD of two numbers.

2. Define a function that uses the GCD function to calculate the LCM.

3. Invoke the LCM function and pass in the two numbers.

4. Print the calculated LCM.

3. Code Program

# Recursive function to find the GCD of two numbers
def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

# Function to find LCM using the GCD function
def lcm(a, b):
    return abs(a*b) // gcd(a, b)

# Two numbers to find the LCM of
num1 = 21
num2 = 14
# Calculate the LCM
lcm_result = lcm(num1, num2)
# Print the LCM
print(f"The LCM of {num1} and {num2} is: {lcm_result}")

Output:

The LCM of 21 and 14 is: 42

Explanation:

1. gcd is a helper function that uses recursion to find the GCD of a and b. It returns a when b is zero, which is the base case, otherwise, it calls itself with b and a % b.

2. lcm is a function that calculates the LCM of two numbers a and b. It calls the gcd function to get the GCD of a and b and then uses it to compute the LCM using the provided formula.

3. num1 and num2 are defined with the values 21 and 14, respectively.

4. The lcm function is called with num1 and num2 as arguments to calculate lcm_result.

5. The result is printed, indicating that the LCM of 21 and 14 is 42.

6. The use of recursion in gcd and its application in calculating the LCM shows a powerful technique for solving such mathematical problems in Python.