Question

Devise a recursive algorithm to find ${\mathbf{a}}^{\mathbf{2}\mathbf{n}}$a, where a is a real number and n is a positive integer. [Hint: Use the equality${\mathbf{a}}^{\mathbf{2}\mathbf{n}\mathbf{+}\mathbf{1}}\mathbf{=}{\left(a^{2n}\right)}^{\mathbf{2}}$ .]

Short answer

The recursive algorithm is,

$$\begin{gathered} \mathrm{procedure}\mathrm{power}(\mathrm{a}:\mathrm{real}\mathrm{number},\mathrm{n}:\mathrm{positive}\mathrm{integers}) \\ \mathrm{if}\mathrm{n}=1\mathrm{then} \\ \mathrm{return}{\mathrm{a}}^2 \\ \mathrm{else}\mathrm{return}(\mathrm{power}{(\mathrm{a},\mathrm{n}-1))}^2 \end{gathered}$$

Step-by-step solution

Describe the given information

The objective is to write the recursive algorithm for computing ${\mathbf{a}}^{\mathbf{2}\mathbf{n}}$.

Give a recursive algorithm for computing a2n

Call the “power” algorithm and real number and a positive integer .

$\text{procedure power (a: real number,}n\text{: positive integers)}$

When the integer n is 1 , then

$\begin{array}{r}{\mathrm{a}}^{2^{\mathrm{n}}}={\mathrm{a}}^{2^1}\\ ={\mathrm{a}}^2\end{array}$

Therefore,

if n = 1 then

return$a^2$

Use,$a^{2^n}=a^{2^{n-1}\cdot 2}={\left(a^{2^{n-1}}\right)}^2$when n is at least 2.

$\text{else return}(\mathrm{power}(\mathrm{a},\mathrm{n}-1){)}^2$

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

$$\begin{gathered} \mathrm{procedure}\mathrm{power}(\mathrm{a}:\mathrm{real}\mathrm{number},\mathrm{n}:\mathrm{positive}\mathrm{integers}) \\ \mathrm{if}\mathrm{n}=1\mathrm{then} \\ \mathrm{return}{\mathrm{a}}^2 \\ \mathrm{else}\mathrm{return}(\mathrm{power}{(\mathrm{a},\mathrm{n}-1))}^2 \end{gathered}$$

Hence, the required algorithm is shown above.