Given two integers, the GCD is the largest positive integer that divides the two numbers without a remainder. For example, the GCD of 32 and 24 is 8. The loop material presented two non-recursive programs: a while-loop solution based on Euclid’s algorithm and a solution using a for-loop.
Euclid’s algorithm is based on a property that can be expressed recursively:
- GCD(n, m) = m when n = 0
- GCD(n, m) = GCD(m mod n, n) when n > 0
Here is the Python program.
##GCD.py
# Euclid's algorithm for computing the gcd
# Nonrecursive version is discussed in for versus while loop post
# see 02Loops example_12 GCDWhileLoop.py
##non-recursive
def findGCD(n, m):
while n != 0:
gcd = n
n = m % n
m = gcd
return gcd
##recursive
def findGCDRecur(n, m):
if n != 0:
return findGCDRecur(m % n, n)
else:
return m
a = input('Please input the first integer:')
b = input('Please input the second integer:')
print(findGCD(a,b))
print(findGCDRecur(a,b))
For more information on Euclid’s algorithm see
