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));
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;
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