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));

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

Related Posts:

Simple Python Program to Add Two Numbers

Python Program to Find Factorial of a Number using for loop

## Post a Comment

## Post a Comment