递归输出2次幂

之前学了汉诺塔，然后做了几道关于递归的题，一直感觉对递归一知半解，感觉递归的题不能100%做出来，但是做了这道题，感觉递归是有技巧的。
从思路讲起：

首先这是一个简单的求幂的方法。
我们如何得到这个式子呢？
7的二次方是 111，也就是说我们可以把二进制的形式转换成这个公式。
7的这个例子太特殊了，我们想一个普遍的例子：11
11的二进制是 1011，所以11可以写成

这个问题就迎刃而解了。那么怎么得到二进制呢？通过大家熟悉的 先对二取余，再除二就可以得到这个二进制数。

这个题还有一个小点就是，题中给的都是从高位到地位的二进制输出，我们对2取余得到的正好是高位的1.所以我们可以直接通过从后查找的方式，查找1的下标，就恰好可以得到这个关系。
例如： 上边11的例子，求出来的二进制应该为1011，但是通过模2除二，得到的是1101，这里我们不用取反，直接从后查找，查到的1的下标依次为3，1，0.正好符合要求。

第三点就是输出格式的问题，我们可以很轻松的将这道题和递归联系起来。

这个公式中的7和3是大于2的，所以我们可以通过2和1的组合表示7和3
也就是

所以可以表示为

最后粘代码

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
void pow2(int n)
{
    if(n==1) //这里的 1代表2的1次幂 
        cout<<"2";
    else if(n==2)  //2代表2的2次幂 
        cout<<"2(2)";
    else if(n==0)
        cout<<"2(0)"; //0代表2的0次幂 
    else  //2的高次幂可以由 0，1，2来组合表示 
    {
        string res;
        while(n)
        {
            res+=n%2+'0';
            n/=2;
        }
        //cout<<res<<endl;   //转换成二进制后的结果（逆序） 
        int index;
        while((index=res.rfind("1"))!=string::npos)  //从后往前查找 
        {
            if(index>2) //为什么要以2为分界点呢？因为二次幂以下都可以直接表示，但是3次幂就要组合表示。所以输出格式有所变化。 
            {
                cout<<"2(";
                pow2(index);//在这里递归输出 
                res[index]='0';
                cout<<")";
                if((index=res.rfind("1"))!=string::npos) //最后一个加号不用输出 
                    cout<<"+";    
            }
            else
            {
                pow2(index);
                res[index]='0';
                if((index=res.rfind("1"))!=string::npos)
                    cout<<"+";    
            }
        }        
    } 
} 
int main()
{
    int n;
    while(cin>>n)
    {
        if(n==1)
            cout<<"2(0)";
        else if(n==2)
            cout<<"2";
        else if(n==0)
            cout<<"0";
        else 
            pow2(n);
        cout<<endl;    
    }
    return 0;
}