Python Program to Calculate HCF (GCD) Using Recursive Function

This python program uses recursive function to calculate Highest Common Factor (HCF). HCF is also known as Greatest Common Divisor (GCD).

To learn more about recursive implementation of Euclid Algorithm to compute HCF, we encourage you to read Euclidean Algorithm Implementations on Wikipedia.

Also try: Calculate HCF Online

Python Source Code: HCF & LCM using Recursive Function


# Finding HCF (GCD) using Recursive Function

# Defining function

def hcf(a,b):
    if b==0:
        return a
    else:
        return hcf(b, a%b) # this is recursion as hcf() calls itself

# Reading numbers from user
first = int(input('Enter first number: '))
second = int(input('Enter second number: '))

# Function call & displaying output HCF (GCD)
print('HCF or GCD of %d and %d is %d' %(first, second, hcf(first, second)))

HCF & LCM Using Recursive Function Output

Enter first number: 23
Enter second number: 69
HCF or GCD of 23 and 69 is 23