# 0050. Pow(x, n)
###### tags: `Leetcode` `FaceBook` `Medium`
Link: https://leetcode.com/problems/powx-n/
## 思路
递归 O(logn) O(logn)
迭代 O(logn) O(1)
## Code
递归

class Solution {
    public double myPow(double x, int n) {
        int N = n;
        if(N < 0){
            x = 1/x;
            N = -N;
        }
        
        return fastPow(x,N);
    }
    public double fastPow(double x, int N){
        if(N == 0) return 1.0;
        double half = fastPow(x,N/2);
        if(N%2 == 0){
            return half*half;
        }
        else{
            return half*half*x;
        }
    }
}

迭代

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N>=0?fastPow(x,N):1.0/fastPow(x,-N);
    }
    public double fastPow(double x, long N){
        double res = 1;
        while(N!=0){
            if(N%2==1){
                res*=x;
            }
            x = x*x;
            N = N/2;
        }
        return res;
    }
}