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