シミュレーション実装関数pow(x,y),すなわち実装演算x^y(xのy次方)であり,ここでxとyはいずれも整数である.

基本思想は,乗算回数を減らし,計算結果を再利用することである.
例えば、x^4は、1つずつ乗算すると4回の乗算が必要です.このように分解すれば(x^2)*(x^2)は2回の乗算しか必要ありません.x^2の結果は再利用できるからです.対称的な分解指数yを作って、x^(y/2)の平方を求めたほうがいいです.
具体的なアルゴリズムは以下の通りである:1 yが偶数であれば、mypow(x,y/2)*mypow(x,y/2)を直接計算する.2 yが奇数の場合、y−1は偶数であり、第1のケースに戻る.

//int mypow(int x, int y)
//{
//	if (y == 0)
//		return 1;
//	if (y == 1)
//		return x;
//	else
//	{
//		return x*mypow(x, y - 1);
//	}
//		
//}

int mypow(int x, int y){
	if (y == 0) 
		return 1;
	if (y == 1) 
		return x;
	int ret = 0;
	int tmp = mypow(x, y / 2);
	if (y & 1 != 0)
	{
		ret = x*tmp*tmp;
	}
	else
	{
		ret = tmp*tmp;
	}
	return ret;
}

int main()
{
	printf("%d
", mypow(2, 4));
	system("pause");
	return 0;
}