question
Write a recursive power function without using any external libraries.

ex. power(3, 4) should return 34 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. xab = (xa)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: xp

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