Question

For two integers m and n, their GCD(Greatest Common Divisor) can be computed by a recursive function. Write a recursive method gcd(m,n) to find their Greatest Common Divisor. Once m is 0, the function returns n. Once n is 0, the function returns m. If neither is 0, the function can recursively calculate the Greatest Common Divisor with two smaller parameters: One is n, the second one is m mod n. Although there are other approaches to calculate Greatest Common Divisor, your program should follow the instructions of this question, otherwise you will not get the credit. Then write a testing program to call the recursive method.

Answer 1

In Python:

def gcd(m,n):

if n == 0:

return m

elif m == 0:

return n

else:

return gcd(n,m%n)

Step-by-step explanation:

This defines the function

def gcd(m,n):

If n is 0, return m

if n == 0:

return m

If m is 0, return n

elif m == 0:

return n

If otherwise, calculate the gcd recursively

else:

return gcd(n,m%n)

To call the function to calculate the gcd of say 15 and 5 from main, use:

gcd(15,5)