Question

Give a recursive algorithm for computing the greatest common divisor of two nonnegative integers a and b with a < b

Answer 1

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.