50. Pow(x, n)

class Solution {
    public double myPow(double x, int n) {
        if (n == 0) {
            return 1;
        }
        if (n < 0) {
            // return 1 / myPow(x, -n);
            // avoid int overflow.
            return (1 / x) * myPow(1 / x, -(n + 1));
        }
        double half = myPow(x, n / 2);
        if (n % 2 == 0) {
            return half * half;
        } else {
            return half * half * x;
        }
    }
}