力扣50. Pow(x, n)

递归

• 思路：
  • n >= 0 时：
    • n 为偶数时，x ^ n = x^(n / 2) * x^(n / 2)
    • n 为奇数时，x ^ n = x^(n / 2) * x^(n / 2) * x
    • n = 0 时， x^0 = 1
  • 当 n < 0 时：
    • x ^ n = 1.0 / x^(-n)

class Solution {
public:
    double myPow(double x, int n) {
        long long N = n;

        return (N >= 0) ? quickMulti(x, N) : 1.0 / quickMulti(x, -N);
    }

private:
    double quickMulti(double x, long long n) {
        if (n == 0) {
            return 1.0;
        }

        double y = quickMulti(x, n / 2);

        return (n % 2 == 0) ? y * y : y * y * x;
    }
};