Python Program to Find GCD Using Recursion

You can find the GCD of two numbers using recursion in Python by defining a function like def gcd(a, b): return a if b == 0 else gcd(b, a % b) which calls itself until the remainder is zero.

Examples

Inputgcd(48, 18)

Output6

Inputgcd(100, 25)

Output25

Inputgcd(7, 3)

Output1

How to Think About It

To find the GCD using recursion, think about the fact that the GCD of two numbers also divides their difference. We use the remainder operation % to reduce the problem size. If the second number is zero, the first number is the GCD. Otherwise, we call the function again with the second number and the remainder of the first number divided by the second.

Algorithm

1

Get two numbers as input.

2

Check if the second number is zero.

3

If yes, return the first number as the GCD.

4

If no, call the function recursively with the second number and the remainder of the first number divided by the second.

5

Repeat until the second number becomes zero.

Code

python

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

print(gcd(48, 18))

Output

6

Dry Run

Let's trace gcd(48, 18) through the code

1

Initial call

gcd(48, 18) checks if 18 == 0 (false), calls gcd(18, 48 % 18)

2

Second call

gcd(18, 12) checks if 12 == 0 (false), calls gcd(12, 18 % 12)

3

Third call

gcd(12, 6) checks if 6 == 0 (false), calls gcd(6, 12 % 6)

4

Fourth call

gcd(6, 0) checks if 0 == 0 (true), returns 6

5

Return values

Each call returns 6 back up the chain to the original call

Call	a	b	a % b	Return
1	48	18	12	gcd(18, 12)
2	18	12	6	gcd(12, 6)
3	12	6	0	gcd(6, 0)
4	6	0	-	6

Why This Works

Step 1: Base case

When the second number b is zero, the first number a is the GCD, so the function returns a.

Step 2: Recursive call

If b is not zero, the function calls itself with b and the remainder of a divided by b, reducing the problem size.

Step 3: Repeating until base case

This process repeats, shrinking the numbers until the remainder is zero, ensuring the GCD is found.

Alternative Approaches

Using while loop (iterative)

python

def gcd_iterative(a, b):
    while b != 0:
        a, b = b, a % b
    return a

print(gcd_iterative(48, 18))

This method uses a loop instead of recursion, which can be easier to understand for some and avoids recursion depth limits.

Using math.gcd function

python

import math

print(math.gcd(48, 18))

Python's built-in math module has a gcd function that is optimized and simple to use.

Complexity: O(log(min(a, b))) time, O(log(min(a, b))) space

Time Complexity

Each recursive call reduces the problem size roughly by the remainder, which decreases quickly, leading to a logarithmic time complexity.

Space Complexity

The recursion stack grows with the number of calls, which is proportional to the logarithm of the smaller input.

Which Approach is Fastest?

The built-in math.gcd is fastest and most optimized, followed by the iterative approach which avoids recursion overhead.

Approach	Time	Space	Best For
Recursive gcd	O(log(min(a,b)))	O(log(min(a,b)))	Learning recursion and simplicity
Iterative gcd	O(log(min(a,b)))	O(1)	Avoiding recursion overhead
math.gcd	O(log(min(a,b)))	O(1)	Best performance and simplicity