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 1000500`

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
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.

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