Using Python!!! Write a recursive function gcd(m,n) that returns the greatest co

Question

Using Python!!!

Write a recursive function gcd(m,n) that returns the greatest common divisor of a pair of numbers. The gcd of m and n is the largest number that divides both m and n. If one of the numbers is 0, then the gcd is the other number. If m is greater than or equal to n, then the gcd of m and n is the same as the gcd of n and m-n. If n is greater than m, then the gcd is the same as the gcd of m and n-m.

>>> gcd(5,0)

5

>>> gcd(15,5)

5

>>> gcd(5,7)

1

>>> gcd(24,144)

24

>>> gcd(124,144)

4

Explanation / Answer

from math import *

def gcd(a,b):
   """Finds the greatest common divisor of a and b

   a: Positive integer
   b: Positive integer
   """
   if type(a) != int or type(b) != int:
       return 'a and b must be integers'

   elif a < 0 or b < 0:
       return 'a and b must be positive'
   if b == 0:
       return a
   else:
       return gcd(b, a % b)

#Test gcd
print 'The gcd of 3 and 9 is', gcd(3,9)
print 'The gcd of 27 and 14 is', gcd(27,14)
print 'The gcd of 125 and 15 is', gcd(125,15)

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.