Next
1. Count Digits Recursively2. Reverse Number Recursively3. Check Palindrome Recursively4. Product of Digits Recursively5. GCD Recursively6. Convert Number to Binary Recursively7. Print Digits in Words8. Sum of First N Even Numbers Recursively9. Sum of First N Odd Numbers Recursively10. nCr Recursively (Pascal Formula)

GCD Recursively

Find GCD using Euclidean algorithm recursively.

IntermediatePhase 3 - Level 2: Advanced RecursionExample 5 of 10
gcd-recursively.py
1def gcd(a, b):
2    # Base case
3    if b == 0:
4        return a
5    
6    # Recursive case (Euclidean algorithm)
7    return gcd(b, a % b)
8

9# Test
10a = int(input("Enter first number: "))
11b = int(input("Enter second number: "))
12result = gcd(abs(a), abs(b))
13print(f"GCD: {result}")

Output

Enter first number: 48
Enter second number: 18
GCD: 6

What's going on

Euclidean algorithm: GCD(a,b) = GCD(b, a%b).

Key Concepts:

Base case: b == 0, answer is a
Recursive: GCD(b, a % b)
Continues until remainder is 0

🔗Related Content

PreviousProduct of Digits RecursivelyNextConvert Number to Binary Recursively