GCD of Two Numbers Using Recursion

In this class, we write a program to find GCD of Two Numbers Using Recursion.

For Complete YouTube Video: Click Here

GCD of Two Numbers

The reader should have prior knowledge of recursion. For practice, Click here.

These examples are very helpful in placement exams. Follow our placement training course to crack placement exams easily.

Take an example and understand the GCD of two numbers.

GCD means greatest common divisor.

Example:

The two numbers are 36 and 24.

The numbers 36 and 24 both are divisible by 2.

Both the numbers are divisible by 3.

In the same way, both the numbers are divisible by 4,6, and12.

Out of all the numbers that are dividing 36 and 24. 12 is the greatest number.

GCD of 36 and 24 is 12.

Logic

From the given numbers, identify the maximum and minimum number.

In our example maximum number is 36. and the minimum number is 24.

Do maximum number modulus minimum number.

34 % 24 = 12

Next time maximum number is considered 24, and output is considered the minimum number, i.e. 12.

24 % 12 = 0

Next time maximum number is 12, and the minimum is zero.

Repeat until the minimum number is zero.

12 % 0 stop.

We stop if the minimum number is zero. And the maximum number is taken as our output.

In our example, 12 is our output.

Analyze the program given below for better practice.

Program

num1=int(input("enter your first number"))
num2=int(input("enter your second number"))
if num1<num2:
    minimum=num1
    maximum=num2
else:
    minimum=num2
    maximum=num1
def gcd(maximum,minimum):
    if minimum==0:
        return maximum
    else:
        return gcd(minimum,maximum % minimum)
result=gcd(maximum,minimum)
print(result)