Multiplying x by itself n times takes n steps. There is a much faster idea: since x**8 == (x**4)**2, you can compute x**(n//2) once and square it. Each recursive call halves n, so only about log2(n) multiplications are needed.
Implement power(x, n) that returns x raised to the integer power n without using **, pow() or math.pow. n may be negative, in which case x**n == 1 / x**(-n).
Examples
Input: x = 2, n = 10
Output: 1024
Input: x = 2.0, n = -2
Output: 0.25
Input: x = -2, n = 3
Output: -8
Constraints
xis an int or float,x != 0whenn < 0-10**6 <= n <= 10**6- A solution that recurses once per unit of
nwill exceed the recursion limit on largen.
Goals
- Halve the problem size at each recursive step instead of shrinking it by one
- Handle even/odd cases and negative exponents in a recursion
- Recognise O(log n) recursion depth versus O(n)