1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    double powstep(double x,int n) {
        if(n == 0)return 1.0;
        if(n == 1)return x;
        if(n == 2)return x*x;
        if(n % 2 == 0) {
            return powstep(powstep(x,n/2),2);
        }
        else {
            return x * powstep(powstep(x,n/2),2);
        }
    }
    double pow(double x, int n) {
        int flag = 1;
        if(n < 0)
            flag = -1;
        n = (-1)*n;
        double ans = powstep(x,n);
        if(flag == -1)
            ans = 1.0 / ans;
        return ans;
    }
};