请享用美味的快速幂算法-通俗易懂版

一、算法整体思路

第1步

　　按照最直接、最好理解的方式看，2的n次幂是n个2相乘，即有如下公式

　　例如：

第2步
　　然而为了节省大量时间，通过简单的思考和严格数学推理，我们不难理解以下结论：
　　1.偶数幂的情况:
　　　　通过幂函数运算法则，有2ⁿ=（2^n/2）²，即有如下等式：

　　　　例如2⁴　的计算过程如下所示：

　　　　得到上面的表达式后，2²是不是可以继续按照这个思想分解下去？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;
}

希望能帮助到你，祝你学有所成！