Back to Practice Dashboard
Python BasicsMedium
HCF using Recursion
Learn how to solve the 'HCF using Recursion' problem. This detailed resource details brute force and optimized approaches.
Problem Statement
Medium
Write a function hcf(a, b) that computes the Highest Common Factor (HCF), also known as the Greatest Common Divisor (GCD), of two positive integers a and b using recursion. Use the Euclidean algorithm: HCF(a, b) = HCF(b, a % b), with the base case HCF(a, 0) = a.
Constraints
- •1 <= a, b <= 10^6
Examples
Example 1
Input
a = 12, b = 8
Output
4
Explanation
12 = 4*3, 8 = 4*2. The largest common factor is 4.
Example 2
Input
a = 54, b = 24
Output
6
Explanation
54 = 6*9, 24 = 6*4. HCF is 6.
Example 3
Input
a = 17, b = 13
Output
1
Explanation
17 and 13 are both prime and share no common factors other than 1.
Need a Hint?
Use simple arithmetic operators (like modulo `%`, division `//`), conditional checks, or loops to inspect number properties.
Edge Cases to Watch
- Empty list or null input variables
- Single item lists/arrays
- Extremely large input bounds causing integer or stack overflow
Ready to Solve?
Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.