Final answer:
To compute the greatest common divisor of two nonnegative integers a and b using a recursive algorithm, use the Euclidean algorithm.
Step-by-step explanation:
To compute the greatest common divisor (GCD) of two nonnegative integers a and b with a < b using a recursive algorithm, you can use the Euclidean algorithm. Here is the recursive algorithm:
If b is equal to 0, then the GCD of a and b is a. Return a.
Otherwise, recursively call the algorithm with b as the new value of a and the remainder of dividing a by b as the new value of b.
Here is an example:
Example:
a = 15, b = 35
Step 1: Since b is not equal to 0, we call the algorithm recursively with a = 35 and b = 15 (35 % 15 = 5).
Step 2: Since b is not equal to 0, we call the algorithm recursively with a = 15 and b = 5 (15 % 5 = 0).
Step 3: b is now equal to 0, so the GCD of 15 and 35 is 5. Return 5.