请享用美味的快速幂算法-通俗易懂版
一、算法整体思路
第1步
按照最直接、最好理解的方式看，2的n次幂是n个2相乘，即有如下公式
例如：
第2步
然而为了节省大量时间，通过简单的思考和严格数学推理，我们不难理解以下结论：
1.偶数幂的情况:
通过幂函数运算法则，有2n=（2n/2）2，即有如下等式：
例如24 的计算过程如下所示：
得到上面的表达式后，22是不是可以继续按照这个思想分解下去？of course！现在只是举了一个4次方的例子，我们可以从此得到启发，发现求n次幂最终可以归结为不断的重复这个分解的一个过程，直到幂不能分解（幂为0了）才停下来。
由此，上述过程可以描述为一个递归过程，递归基（递归结束条件）为”幂等于0“。得到以下递归表达式：
小插叙：
解释第二种情况前，有必要说明以下内容，这也是为什么第二种情况存在的原因：
如果n是奇数，我们知道，在计算机中，n/2会舍去小数，这样如果继续按照上述第一步的方法分解，逆推回去，会发现最终得到的幂是n-1；不信，且看下例
2.奇数幂的情况：
好了，现在可以引出第二种情况，就是奇数幂的情况。我们要求得奇数幂的结果，可以从继续步骤1,即按照偶数幂的求法求出最终结果，再附加一个条件是，什么条件呢？
就是在原来的结果上乘上一个2，原因我相信在插叙中已经说的很明白了，它少了1次幂，现在是在补上这一次幂，即：
3.最终递归表达式
那么到现在，我们可以写出完整的递归表达式了，在偶数幂的递归条件下，附加奇数幂的条件即可，即：
第3步
我们现在对于快速幂的求解思路应当是已经十分清晰了，现在我们来写递归函数(C++):
long long int fastpower(int n){ if (n == 0)//递归基 return 1; else if (n % 2 == 0)//偶数幂的情况 return square(fastpower(n / 2)); else//奇数幂的情况 return square(fastpower(n / 2)) * 2; } long long int square(long long int t){ return t * t; }
二、上刑
everybody，现在我们已经完全理清了思路，接下来要把它整成代码吧！
#include<iostream> using namespace std; long long int fastpower(int n);//求解快速幂 long long int square(long long int t);//平方 int main(void){ int n; cin >> n;//输入幂 cout << fastpower(n); //固定模块初始线 cout << endl; system("pause"); return 0; //固定模块终止线 } long long int fastpower(int n){ if (n == 0)//递归基 return 1; else if (n % 2 == 0)//偶数幂的情况 return square(fastpower(n / 2)); else//奇数幂的情况 return square(fastpower(n / 2)) * 2; } long long int square(long long int t){ return t * t; }
希望能帮助到你，祝你学有所成！