Problem Statement
The task is to find the greatest common divisor (GCD) of two numbers using recursion.
Definition
- The greatest common divisor (GCD) of two numbers is the largest number that divides both of them without leaving a remainder.
- The Euclidean algorithm is a classic method to find the GCD using recursion.
- Example: For the input
a = 56, b = 98, the output should be 14 (the GCD of 56 and 98).
Example Inputs
- Input:
a = 56, b = 98
- Output:
14
Explanation: The GCD of 56 and 98 is 14 because 14 is the largest number that divides both 56 and 98 without a remainder.
Approach - Use Recursion
Approach
The Euclidean algorithm for finding the GCD is based on the principle that:
- GCD(a, b) = GCD(b, a % b)
In this approach, we recursively calculate the remainder when dividing the larger number by the smaller number, until one of the numbers becomes zero. The non-zero number at that point will be the GCD.
Steps
- Base Case: If
b = 0, return a (since the GCD of any number and 0 is the number itself).
- Recursive Case: Otherwise, calculate the remainder of
a divided by b and call the function again with b and the remainder as arguments.
- Continue this process until the base case is reached.
Time & Space Complexity
- Time Complexity: O(log(min(a, b))), where
a and b are the two numbers. The Euclidean algorithm runs in logarithmic time because it reduces the size of the numbers at each step.
- Space Complexity: O(log(min(a, b))) due to the recursive call stack.
Code Snippet
Dry Run
Let’s dry run the code with the input a = 56, b = 98:
- gcd(56, 98):
98 % 56 = 42, so call gcd(56, 42).
- gcd(56, 42):
56 % 42 = 14, so call gcd(42, 14).
- gcd(42, 14):
42 % 14 = 0, so return 14.
Output:
- Result: 14 (since 14 is the greatest common divisor of 56 and 98).
Complexity Analysis
Time and Space Complexity
- Time Complexity: O(log(min(a, b))) due to the Euclidean algorithm’s efficiency.
- Space Complexity: O(log(min(a, b))) due to the recursion stack.
Conclusion
The Euclidean algorithm for finding the GCD is a very efficient method, especially when implemented recursively. The time complexity of O(log(min(a, b))) makes it much faster than brute-force methods. It’s a simple yet powerful technique for solving this problem. While recursion introduces some space complexity, it's a trade-off for a clean and elegant solution.