Solution Review: Find the Greatest Common Divisor

This review provides a detailed analysis of the solution to find the greatest common divisor.

We'll cover the following

Solution: Using Recursion

Press + to interact
def gcd(testVariable1, testVariable2) :
  # Base Case
  if testVariable1 == testVariable2 :
    return testVariable1
  # Recursive Case
  if testVariable1 > testVariable2 :
    return gcd(testVariable1 - testVariable2, testVariable2)
  else :
    return gcd(testVariable1, testVariable2 - testVariable1)
# Driver Code
number1 = 6
number2 = 9
print(gcd(number1, number2))

Explanation

The naive approach to finding GCDGCD of 22 numbers is to list all their divisors. Then pick the common divisors, and then select the greatest out of them.

However, a simple mathematical simplification can make our task easier.

The idea behind calculating GCDGCD is: If m>nm>n, GCD(m,n)GCD(m,n) is the same as GCD(m−n,n)GCD(m-n,n).

This is because if m/dm/d and n/dn/d both leave no remainder, then (m−n)/d(m-n)/d leaves no remainder.

This leads to the following algorithm:

gcd(m,n)={mifm==n,gcd(m−n,n)ifm>n,gcd(m,n−m)ifm<n,gcd(m,n) = \begin{cases} m \:\:\:\:\:\:\:\:\:\:\: if \:m == n, \\ gcd(m-n, n) \:\:\:\:\: if \:m > n, \\ gcd(m, n-m) \:\:\:\: if \:m < n, \end{cases}

Let’s have a look at the code execution:

In the next lesson, we have another challenge for you to solve.