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):
        return a;
    return gcd(b,a%b);

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


Enter Two Numbers:500 1000

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 using for loop

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
	    for i in range(1,mn+1):
	        if(A%i==0 and B%i==0):
	    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.

If you have doubts let me know in the comment section.

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