Power of X (Pow(x, n))

Difficulty: Medium

Problem

Implement pow(x, n), which calculates x raised to the power n (i.e., x^n). The function should handle negative exponents as well. Solve it using recursion.

Example

Input: x = 2.0, n = 10
Output: 1024.0
Explanation: 2^10 = 1024.0

Brute-force approach

This is a recursion-focused problem. We go directly to the recursive solution using the Leap of Faith approach.

Time complexity: - · Space complexity: -

Optimal approach

Key insight: If someone magically gives you x^(n/2), then x^n = (x^(n/2))². Trust the recursion, square the result!

Use the Leap of Faith recipe to build a recursive fast power solution. Trust that myPow(x, n/2) works, then square the result.

Steps

1. Base case: if n == 0, return 1
2. If n < 0, return 1 / myPow(x, -n)
3. If n is even: half = myPow(x, n/2), return half × half
4. If n is odd: return x × myPow(x, n-1)

Time complexity: O(log n) · Space complexity: O(log n)