Question

Devise a recursive algorithm for computing the greatest common divisor of two nonnegative integers a and b with using the fact that gcd (a,b) = gcd (a,b - a) .

Short answer

The recursive algorithm is,

$$\begin{gathered} \mathrm{procedure}\gcd (\mathrm{a},\mathrm{b}:\mathrm{positive}\mathrm{integers}\mathrm{with}\mathrm{a}<\mathrm{b}) \\ \mathrm{if}\mathrm{a}=0\mathrm{then} \\ \mathrm{return}\mathrm{b} \\ \mathrm{else} \\ \mathrm{if}\mathrm{a}=\mathrm{b}-\mathrm{a}\mathrm{then}\mathrm{return}\mathrm{a} \\ \mathrm{else}\mathrm{if}\mathrm{a}<\mathrm{b}-\mathrm{a}\mathrm{then}\mathrm{return} \\ \gcd (\mathrm{a},\mathrm{b}-\mathrm{a}) \\ \mathrm{else}\mathrm{return}\gcd (\mathrm{b}-\mathrm{a},\mathrm{a}) \end{gathered}$$

Step-by-step solution

Describe the given information

The objective is to write the recursive algorithm for finding the greatest common divisor of two nonnegative integers a and b.

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

Call the algorithm "greatest divisor" and the input are two positive integers and with a < b .

$\text{procedure}\gcd (a,b:\text{positive integers with}a<b)$

When one of the integers is zero, then the greatest common divisor is the other integer.

if a = 0 then

return b

Since gcd (a,b = gcd (a,b-a) when is nonzero.

$$\begin{gathered} \mathrm{else} \\ \mathrm{if}\mathrm{a}=\mathrm{b}-\mathrm{a}\mathrm{then}\mathrm{return}\mathrm{a} \\ \mathrm{else}\mathrm{if}\mathrm{a}<\mathrm{b}-\mathrm{a}\mathrm{then}\mathrm{return} \\ \gcd (\mathrm{a},\mathrm{b}-\mathrm{a}) \\ \mathrm{else}\mathrm{return}\gcd (\mathrm{b}-\mathrm{a},\mathrm{a}) \end{gathered}$$

By combining all the steps, the required algorithm will be as follows.

$$\begin{gathered} \mathrm{procedure}\gcd (\mathrm{a},\mathrm{b}:\mathrm{positive}\mathrm{integers}\mathrm{with}\mathrm{a}<\mathrm{b}) \\ \mathrm{if}\mathrm{a}=0\mathrm{then} \\ \mathrm{return}\mathrm{b} \\ \mathrm{else} \\ \mathrm{if}\mathrm{a}=\mathrm{b}-\mathrm{a}\mathrm{then}\mathrm{return}\mathrm{a} \\ \mathrm{else}\mathrm{if}\mathrm{a}<\mathrm{b}-\mathrm{a}\mathrm{then}\mathrm{return} \\ \gcd (\mathrm{a},\mathrm{b}-\mathrm{a}) \\ \mathrm{else}\mathrm{return}\gcd (\mathrm{b}-\mathrm{a},\mathrm{a}) \end{gathered}$$

Therefore, the recursive algorithm is shown above.