GCD of Two Numbers in Python Using Recursion

The Highest Common Factor (HCF), commonly known as GCD, may be calculated in Python using just one function provided by the math module, which can simplify jobs in a variety of circumstances.

This code is written in Python to find the greatest common divisor (GCD) of two numbers using recursion. Recursion is a programming technique in which a function calls itself until a certain condition is met.

Python Program to Get GCD of Two Numbers Using Recursion

The program takes two numbers as input and converts them to integers, before assigning them to the variables a and b. The gcd() function is then defined, which takes two parameters – a and b.

The function checks if the second number is equal to 0, and if it is, it returns the first number as the GCD. If it is not, then the function calls itself, swapping the values of a and b and passing in b as the first parameter and a modulo b as the second parameter.

Doing this ensures that the function will eventually reach the base case of b being equal to 0, at which point it will return a as the GCD of the two numbers.

Here, two integers stored in variables num1 and num2 are passed to the compute_hcf() function. The function computes the H.C.F. of these two numbers and returns it.

In the function, we first determine the smaller of the two numbers since the H.C.F. can only be less than or equal to the smallest number. We then use a for loop to go from 1 to that number.

In each iteration, we check if our number perfectly divides both the input numbers. If so, we store the number as H.C.F. At the completion of the loop, we end up with the largest number that perfectly divides both the numbers.

Finally, the program calls gcd() with a and b as parameters and prints the GCD. This code will calculate the GCD of two numbers using recursion, in python, entered by the user.

# GCD of Two Numbers in Python Using Recursion

def gcd(a,b):
	if(b==0):
    	return a
	else:
    	return gcd(b,a%b)

# we are taking a number from user as input
# entered value will be converted to int from string
a=int(input("Enter first number:"))
b=int(input("Enter second number:"))

GCD=gcd(a,b)
print("GCD is: ",GCD)

Output:

Enter first number:15
Enter second number:20
GCD is:  5

The program first asks the user to enter two numbers, and these are stored in the variables a and b. Then, the GCD of the two numbers is calculated using a function that uses recursion. Finally, the GCD is printed with the output “GCD is: “, in this case, “GCD is: 5”.

So, the output “Enter first number: 15 Enter second number: 20 GCD is: 5” indicates that the GCD of two numbers using recursion is 5 fo the numbers 15 and 20.

Euclidean algorithm

This approach is based on the observation that the HCF of any two integers divides the difference between them as well.

We divide the bigger by the smaller and then take the residual in this procedure. Divide the smaller by the remaining amount now. Continue until there is nothing left.

To get the H.C.F. of 54 and 24, for instance, we divide 54 by 24. There are 6 units left. Once we divide 24 by 6, the residue is equal to zero. 6 is hence the necessary H.C.F.

For More Python Programming Exercises and Solutions check out our Python Exercises and Solutions