GCD Recursively
Find a GCD with Euclid's recursive algorithm. Students trace remainders, argument swapping, absolute values, and a zero second argument as the base case.
1def gcd(a, b):2 # Base case3 if b == 0:4 return a56 # Recursive case (Euclidean algorithm)7 return gcd(b, a % b)89# Test10a = 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
In this one
- Apply Euclid's identity
- Reduce through remainders
- Handle a zero second argument
How it works
- 1
Pass absolute inputs to gcd.
- 2
Return a when b is zero.
- 3
Otherwise recurse with b and a % b.
Walk through GCD Recursively
gcd(18, 12)
- 1.The first recursive pair is (12, 6).
- 2.The next pair is (6, 0).
- 3.The zero-second-argument base case returns 6.
Edge cases
What is gcd(12, 0)?
What is gcd(12, 0)?
Twelve, returned immediately.
What does this implementation return for gcd(0, 0)?
What does this implementation return for gcd(0, 0)?
Zero, a conventional programming result for that case.
What's going on
gcd(a, b) becomes gcd(b, a % b). The second value gets smaller for nonnegative arguments, eventually reaching zero.
When b is zero, a is returned without attempting modulo by zero. abs makes the public result nonnegative. The call stack stores the short chain of pending returns; this avoids scanning every possible factor as the basic loop version does.
What is gcd(12, 0)? Twelve, returned immediately.
What does this implementation return for gcd(0, 0)? Zero, a conventional programming result for that case.
Quiz
Tap an option. The answer stays hidden until you pick.
Question 1
Which recursive pair is used?
Pick an answer to check it.
Question 2
What is gcd(12, 0)?
Pick an answer to check it.
Questions people ask
What is gcd(12, 0)?
Twelve, returned immediately.
What does this implementation return for gcd(0, 0)?
Zero, a conventional programming result for that case.
Which recursive pair is used?
b, a % b.
๐Related Content
- ๐
Phase 3 - Learn Concepts
Review Phase 3 concepts and explanations
- ๐
Phase 3 - Quiz
Test your Phase 3 understanding with quiz questions
- ๐ป
Phase 3 - All Practice Problems
Explore all practice problems for Phase 3
- ๐
Master Your Logic Building - Complete Course
Browse all phases and tutorials
- ๐ง
Logic Building Overview
Learn about the complete logic building curriculum