# 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;
```

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.