Python program to find h.c.f. of two numbers using recursion

find h.c.f. of two numbers

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:

Python program for h.c.f. of two numbers using recursion

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:-

Python program to calculate g c d of two numbers using recursion

Output 2:

Python program to calculate h.c.f. of two numbers using recursion

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:-

Python program for h.c.f. of two numbers using recursion