【遞歸】高效率求2的n次幂

思路：使用翻一番的技巧。

比如，2的9次 則 1 * 2 = 2；2 * 2 = 4；4 * 4 =16；16 * 16=。。。；

指數：1-----------2-----------4------------8---------------

對應代碼：

能翻倍的情況下

//能翻
while((ex<<1)<n) {
			//翻
			res = res * res;
			//指數實際增長
			ex<<=1;
		}
           

不能翻倍的情況下

不能翻：則把內插補點作為指數遞歸計算。

當內插補點為0時，就說明到頭了，隻剩最後一個數字。 return 1 。乘數字本身即可。

代碼如下

static int pow (int a,int n) {
		if( n == 0){
			return 1;
		}
		int res = a;
		int ex = 1;
		//判斷能不能翻倍
		while((ex<<1)<n) {
			//翻
			res = res * res;
			//指數實際增長
			ex<<=1;
		}
		//不能翻：則把內插補點作為指數遞歸計算。
		// 當內插補點為0時，就說明到頭了，隻剩最後一個數字。 return 1 。乘數字本身即可。
		return res*pow(a, n-ex);
	}
	
	public static void main(String[] args) {
		System.out.println(pow(2, 3));
	}