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.
Algorithm to find h.c.f. of two numbers using recursion
Step 1: Start
Step 2: Create a user-defined function gcd() which will take 2 integer arguments.
Step 3: take two inputs from the user for finding the H.C.F.
Step 4 print gcd( num1, num2)
Step 5: Stop
Python code to find h.c.f. of two numbers using recursion
Output 1:
Explanation:
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:
Explanation:
For the inputs 12 and 8, which are then passed as an argument in recursive function gcd().
The recursive function behaves in such way:-
