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. 

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 both are the same thing. 

GCD of 6 & 9 is 3 

Write a Program to find 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 minimum of A & B and when we found a number which is a factor of both A and B. Then we store it in answer variable. In 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 am including 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

Related Posts

Post a Comment