Looking for jobs/internships? Click Here!

GCD of two numbers in Python using recursion

In this program, we are going to make a python program to calculate the GCD of two numbers using recursion.

 In this program, we will make a python program to calculate the GCD of two numbers using recursion. 

GCD stands for the greatest common divisor. Sometimes, they can ask you to write a program for HCF of two numbers, so don't worry about this because they are the same thing. 

Ex: GCD of 6 & 9 is 3 

Write a Program to find the gcd of two numbers in python using Recursion.

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

str = input("Enter Two Numbers:")
a, b = str.split()
a=int(a)
b=int(b)
print(gcd(a,b));
Output for gcd of two numbers in python:

Enter Two Numbers:500 1000
500

According to Euclid algorithm,  GCD(a,b)=GCD(b,a%b). The base case for our recursive function is if b is zero, then we will return a.

The time complexity of GCD of two numbers in Python using Recursion is O(log(max(a,b)).

GCD of Two numbers in Python

In this approach, we are simply iterating from 1 to a minimum of A & B, and when we find a number, that is a factor of both A and B. Then, we store it in the answer variable. This way, we get the highest common factor of A and B.

def gcd(self, A, B):
        # code here
        mn=min(A,B)
	    ans=1
	    for i in range(1,mn+1):
	        if(A%i==0 and B%i==0):
	            ans=i;
	    
	    return ans;
GCD of Two numbers in Python


The time complexity of this approach is O(min(A, B)), which is slower than our previous log(n) approach. It gives a time limit exceeded when 1 ≤ A, B ≤ 109



How to find gcd of two numbers in python

Here, I include the video of code with harry to find the gcd of two numbers in Python for a better understanding of this question.

Related Posts:
Simple Python Program to Add Two Numbers
Python Program to Find Factorial of a Number using for loop

Post a Comment

Please do not enter any spam link in the comment box.