Authors:
Y Daniel Lang
Chapter:
5.recursion
Exercise:
Programming Excercises
Question:3 | ISBN:978013274719 | Edition: 6
Question
(Compute greatest common divisor using recursion) The gcd(m, n) can also be defined recursively as follows:
■ If m % n is 0, gcd(m, n) is n.
■ Otherwise, gcd(m, n) is gcd(n, m % n).
Write a recursive function to find the GCD. Write a test program that prompts the user to enter two integers and displays their GCD.
Answer
A test program that prompts the user to enter two integers and displays their GCD::
CODE:
def GCD(m,n): #defining gcd function.
gcd = 1 #initialising gcd.
if m % n == 0: #check whether m is divisible by n with reminder 0.
return n #if yes, return n.
for i in range(n // 2, 0, -1): #if not follow the loop.
if m % i == 0 and n % i == 0:
gcd = i
break
return gcd #display gcd value
num1 = int(input("enter 1st integer:")) #take inputs fromm the user.
num2 = int(input("enter 2nd integer:"))
print("GCD of given two numbers is",GCD(num1,num2)) #display thier gcd
OUTPUT:
enter 1st integer:14
enter 2nd integer:2
GCD of given two numbers is 2
enter 1st integer:24
enter 2nd integer:20
GCD of given two numbers is 4