Editor

Python Program to Find the GCD Using Recursion

Beginner · Recursion

The GCD (greatest common divisor), also called the HCF (highest common factor), of two numbers is the largest number that divides both of them exactly, so the GCD of 48 and 18 is 6. This program uses Euclid's algorithm, which says the GCD of a and b is the same as the GCD of b and a % b. That rule calls itself on smaller numbers, so it is naturally recursive.

Program

gcd_using_recursion.py
def gcd(a, b):
# Base case: the GCD of a number and 0 is the number itself
if b == 0:
return a
# Recursive step: gcd(a, b) is the same as gcd(b, a % b)
return gcd(b, a % b)
a = 48 # or: a = int(input("Enter the first number: "))
b = 18 # or: b = int(input("Enter the second number: "))
result = gcd(a, b)
print(f"GCD of {a} and {b} is {result}")
# The LCM follows from the GCD, because a x b = GCD x LCM
print(f"LCM of {a} and {b} is {a * b // result}")
Output
GCD of 48 and 18 is 6
LCM of 48 and 18 is 144

How it works

  1. Euclid's rule works because any number that divides both a and b also divides a % b, the remainder when a is divided by b, so gcd(a, b) equals gcd(b, a % b).
  2. Each call works with smaller numbers: gcd(48, 18) becomes gcd(18, 12), then gcd(12, 6), then gcd(6, 0).
  3. The base case is b == 0, because every number divides 0, so the GCD of a and 0 is a, here 6.
  4. The LCM (lowest common multiple) is then a * b // result, because the product of two numbers equals their GCD times their LCM.

Other ways to write it

Showing each step

Showing each step
def gcd(a, b, step=1):
print(f"Step {step}: gcd({a}, {b})")
if b == 0:
return a
return gcd(b, a % b, step + 1)
print("Answer:", gcd(252, 105))
Output
Step 1: gcd(252, 105)
Step 2: gcd(105, 42)
Step 3: gcd(42, 21)
Step 4: gcd(21, 0)
Answer: 21

Printing each call shows how quickly the numbers shrink: 252 and 105 need only four calls to reach the answer, 21.

Using subtraction

Using subtraction
import math
def gcd(a, b):
if a == b: # base case: equal numbers are their own GCD
return a
if a > b:
return gcd(a - b, b)
return gcd(a, b - a)
print("GCD of 48 and 18:", gcd(48, 18))
print("Check with math.gcd():", math.gcd(48, 18))
Output
GCD of 48 and 18: 6
Check with math.gcd(): 6

Euclid's original method subtracts the smaller number from the larger until they are equal, which takes more calls than the % version and only works for positive numbers; math.gcd() is the built-in way.

Try it yourself

Find the GCD of three numbers, 36, 60 and 84, by calling gcd() twice.

Edit the program above and press Run, or open it in the full editor to save it and share it. To watch it run line by line, open it in the visualizer.

Related programs

All Python programs · CBSE class 12 practical file · Python exercises