Quiz Question 1 of 5
In Euclid's recursive method for finding the GCD, what is the impact on the number of recursive calls when the two integers are relatively prime (i.e., their GCD is 1)?
Choose the correct answer below:
-
A
The number of recursive calls is minimized because the algorithm quickly identifies that the two numbers share no common divisors.
-
B
The number of recursive calls is zero because the base case is reached immediately.
-
C
The number of recursive calls is maximized because the algorithm has to fully reduce one of the numbers to 1.
-
D
The number of recursive calls is independent of whether the integers are relatively prime; it depends only on the difference between the numbers.