快速幂運算（遞歸）

1. 問題描述：

求解出結果在Long範圍内的 n 的 x 次幂

2. 思路分析：

① 使用傳統計算累乘的方法時間時間複雜度O(n)，我們可以對其進行優化，使用的是反複平方的方法來進行求解，反複平方的話相當于以2的指數的速度靠近x，這樣的計算速度是很快的

② 因為每一次指數都是以2的倍數增長的，是以在循環中隻能求解出x的偶數次幂（假設目前到的結果是x的y次幂），是以我們要對剩下來的n的x - y次幂進行求解，對于同樣的問題我們可以使用遞歸來進行求解，在方法中把剩下來的x - y次傳給遞歸方法求解，假如x為偶數的話，最終參數會變為零，這個時候傳回1就可以了，但是求解的有可能是奇數那麼最後的x的參數肯定是1那麼傳回自身就可以了

③ 需要注意的是我們一開始的時候要把n先進行平方，因為接下來的循環中每一次幂數都是要乘以2的，是以不能夠為零，為零的話就陷入了死循環了

3. 代碼如下:

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int x = sc.nextInt();
		long res = exponent(n, x);
		System.out.println(res);
		sc.close();
	}

	private static long exponent(int n, int x) {
		if(x == 0)return 1;
		//因為它可能最後隻剩下n的一次幂(每一次減去的都是2次方但是要求解的可能是奇數次)
		//是以這也是一個出口
		if(x == 1){
			return n;
		}
		//注意這裡先要乘以自己因為times作為判斷不能夠一開始等于零是以需要現在這裡預處理一下
		long res = n * n;
		int times = 2;
		while(times * 2 <= x){
			res = res * res;
			//注意下面的是乘以2而不是加2
			times *= 2;
		}
		//遞歸求解
		res *= exponent(n, x - times);
		return res ;
	}
}