Search⌘ K
Home
Courses
Recursion for Coding Interviews in Python

Solution Review: Find the Greatest Common Divisor

Explore the use of recursion to solve the problem of finding the greatest common divisor (GCD) of two numbers. Understand the recursive algorithm that simplifies the calculation by reducing the problem step-by-step, and follow the explanation of how recursion breaks down the GCD computation effectively.

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) ...