題目：
請寫一個方法，來計算x的n次方

舉例：
Pow(2,3)應該要等於8

點我前往LeetCode題目

那在開始前不乏提醒一下此系列的固定提醒：

這是一系列逐漸帶入解題的文章，難度會隨著進度增加，若還沒有讀過前面的文章，建議先從最前面開始來逐漸練習解題喔！

是的，既然我們都說這裡是遞迴單元，當然使用一般暴力解是不行的

如果我們單純用for迴圈跑這題會發生什麼事呢？

啊，他就像喝水一樣自然的爆掉了（？？？）

我們都知道x的n次方其實是「x的(n/2)次方做平方」對吧？

所以可以利用這個特性，拿到自己(n/2)次方的結果，做平方後，就可以省下一半的時間。

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

這樣講可能還是有點模糊，我們從程式碼慢慢解釋吧！

double re=0;
if(n==0) return 1;

這裡用了一個re來準備收自己(n/2)次方的結果
那我們知道n的0次方就是1，所以上面第二行就作為n=0時的中止條件（嘿！這個應該不用再解釋對吧XD）

if(n==1) return x;
if(n==-1) return 1.0/x;

這裡要注意的是，題目有可能包含負數次方的，所以遇到負數次方時，我們就要改傳1.0/x回去。

re = myPow(x,n/2);

接著拿自己的(n/2)次方結果回來，注意這裡先別急著平方，我們要額外做一些處理

if(n%2==1) return re*re*x;
else if(n%2== 0) return re*re;
else return re*re/x;

那我們知道，2的4次方就是2的2次方做平方，那2的5次方要怎麼處理？
就是2的2次方做平方後，再乘上一個2

也就是說，這段程式碼是幫助程式在遇到奇數次方時，幫我們多乘上一個x，來避免漏掉東西。而如果n是負數的奇數，則幫我們多乘上一個(1/x)。

可能有人會好奇，上面的看起來，n似乎要是2的?次方才會正常？
其實不會，我們假設n=11吧，那程式會這樣運作：

1. call n=5的自己
2. call n=2的自己
3. call n=1的自己
4. 拿到x
5. 拿到n=2的自己，平方後多乘自己一次
6. 拿到n=5的自己，平方後多乘自己一次
7. 找到答案

大家可以照上面的順序，自己想像一下過程，就可以理解為何不會產生那種問題了

解決！