In this tutorial, we are going to learn writing python program to calculate the Highest Common Factor of two numbers. We will use recursion to calculate the HCF
Problem Statement
For any two numbers that are inputs given by the user, we have to calculate and print the h.c.f. of that numbers.
For example:
Case1: If the user inputs the numbers 4 and 6.
then the output should be ‘2’.
Case2: If the user inputs the numbers 5 and 7.
then the output should be ‘1’.
Our logic to find h.c.f. of two numbers using recursion
- Our program will take two integer inputs from the user.
- Then use gcd(num1, num2) user-defined recursive function that will return the gcd of the given numbers.
Python code to find h.c.f. of two numbers using recursion
def gcd(num1,num2):
if num2 == 0:
return num1;
return gcd(num2, num1 % num2)
#taking inputs from the user
num1 = int(input("Enter first number: "))
num2 = int(input("Enter second number: "))
print("hcf/gcd of",num1,"and",num2,"=",gcd(num1,num2))Output 1:
Enter first number: 8
Enter second number: 6
hcf/gcd of 8 and 6 = 2Explanation:
For the inputs 8 and 6, which are then passed as an argument in recursive function gcd().
The recursive function behaves in such way:-
Output 2:
Enter first number: 12
Enter second number: 8
hcf/gcd of 12 and 8 = 4Explanation:
For the inputs 12 and 8, which are then passed as an argument in recursive function gcd().
The recursive function behaves in such way:-
