Recursion for Coding Interviews in Python/

...

/

Solution Review: Find the Greatest Common Divisor

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

Python 3.5
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 brute force approach to finding GCDGCD of 22 numbers would be to list all their divisors, pick the common divisors, and then select the greatest of them. However, a mathematical simplification can make this task easier.

The process of calculating GCDGCD is as follows: If m>nm>n, then GCD(m,n)GCD(m,n) ...