Compute GCD of Two Numbers Recursively in Python

Suppose we have two numbers a and b. We have to find the GCD of these two numbers in recursive way. To get the GCD we shall use the Euclidean algorithm.

So, if the input is like a = 25 b = 45, then the output will be 5

To solve this, we will follow these steps −

• Define a function gcd() . This will take a, b
• if a is same as b, then
  • return a
• otherwise when a < b, then
  • return gcd(b, a)
• otherwise,
  • return gcd(b, a - b)

Example

Let us see the following implementation to get better understanding −

def gcd(a, b):
   if a == b:
      return a
   elif a < b:
      return gcd(b, a)
   else:
      return gcd(b, a - b)

a = 25
b = 45
print(gcd(a, b))

Input

25, 45

Output

5