[算法提高] 递归 快速幂

理解递归的想法不难，关键是如何 快速 写出 正确 高效 的递归。

函数递归调用的基本形式：

Type MyFunction(){
    ...
    MyFunction();
}

下面以递归实现 快速幂 ，说明一下写递归的一些注意点，这些要点是不是必要的我不知道，我想这需要严格的证明。

一般求幂的方法是调用<cmath>中的pow()函数，例如求我们可以用pow(x, n)函数来得到。(调轮子)

如果要造轮子的话，一种想法是用for循环：

#include <iostream>
#include <cmath>
using namespace std;

int forPower(int x, int n){
	int y = 1;
	for(int i = 0; i < n; i++){
		y = y * x;
	}
	return y;
}

int main() {
	cout << "pow(2,6)=" << pow(2,6) << endl;
	cout << "forPower(2,6)=" << forPower(2,6) << endl;
	return 0;
}

当然，forPower(2,6) = 2 * 2 * 2 * 2 * 2 * 2，执行了五次乘法。即forPower(x, n)的时间复杂度大约是O(n)。可不可以更快呢？

比如对于，2 * 2 * 2 * 2 * 2 * 2 * 2 * 2也可以写作是[(2 * 2) * (2 * 2)] * [(2 * 2) * (2 * 2)]， 即y = 2 * 2; y = y * y; y = y * y, 7次乘法变成了3次。这样一层层的分解计算就可以用递归写出来：

#include <iostream>
#include <cmath>
using namespace std;

long long Power(int x, int n) {
	long long y;
	if (n == 1) { //递归的边界 
		return x;
	}else{
		y = Power(x, n/2); //递归：函数调用自身
		if(n % 2 == 0){
			return y * y; 
		}else{
			return y * y * x;
		}
	}
}

int main() {
	cout << "pow(2,4) = " << pow(2,4) << endl; 
	cout << "Power(2,4) = " << Power(2,4) << endl;
	cout << "pow(2,5) = " << pow(2,5) << endl;
	cout << "Power(2,5) = " << Power(2,5) << endl;
	return 0;
}

对于Power(2,7)，图示描述其运算流程：

因此，个人的看法是，要写好递归，三个东西很重要：

1.向内层的递归 y = Power(x, n/2);

2.向外层的返回 return n % 2 == 0 ? y * y : y * y * x;

3.边界层的返回 return x;

其实很像数学归纳法。

个人浅见，欢迎批评指正！