question

Write a recursive power function without using any external libraries.

ex. power(3, 4) should return 3

ex. power(3, 4) should return 3

^{4}which equals 81
A naive approach would result in O(n). A better approach will run in O(log n).

Using properties of powers:

ex. x

Each subsequent call of power() will divide the exponent by two. This is indicative of O(log n) vs O(n) if we simply decremented the exponent by one with each call. If necessary, refresh your memory on the efficiencies of various O-notations.

parameters: (x is an integer, p >= 0)

return: x

ex. x

^{ab}= (x^{a})^{b}Each subsequent call of power() will divide the exponent by two. This is indicative of O(log n) vs O(n) if we simply decremented the exponent by one with each call. If necessary, refresh your memory on the efficiencies of various O-notations.

parameters: (x is an integer, p >= 0)

return: x

^{p}```
```

**power**(x, p)

**if** p = 0

**return** 1

**if** p is odd

r = power(x, (p – 1) / 2)

**return** x * r * r

**else**

r = power(x, p / 2)

**return** r * r