Question

Use the algorithm in Exercise 24 to devise an algorithm for evaluating${\mathit{a}}^{\mathbf{n}}$ a when is a non-negative integer. [Hint: Use the binary expansion of].

Short answer

Power ( a : real number,: n nonnegative integers)

If n = 0 then return 1.

If n is even then return

Power (a, n / 2).

Else return a.

Power (a, n - 1).

Step-by-step solution

Recursive algorithm

Recursion is a computational problem-solving technique used in computer science where the result is dependent on solutions to smaller instances of the same issue. Recursion uses functions that call themselves from within their own code to address such recursive difficulties.

Find the algorithm to evaluate an when n is a non-negative integer.

Let's call the algorithm “Power”.

Let a is a real number and n is a nonnegative integer.

Now, the algorithm is given as,

Power ( a : real number, n : nonnegative integers)

If n = 0 then return 1.

If nis even then return

Power (a, n / 2).

Else return a.

Power (a, n / 1).

Hence the output is$a^n$ .