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)