递归转递推的一个例子

/* 将　void (int n)
    { 
	  if(n>0) 
	  {
	    p(n-1);
		  p(n-1);
	    cout<<n;
	  }
	  }改为递推
	  */
# include<iostream.h>
# include<stack>
using namespace std;
void p(int n);
void main()
{
    int n;
    stack<int> s;
    cout<<"intput n"<<endl;
    cin>>n;
    p(n);
}
void p(int n)
{
    int L1=-1,L2=-2,x;
	int tmp,flag;
    stack<int> s1,s2;
    tmp=n;
    flag=0;                              //flag为退出的标志
    while(n>0||!s1.empty())   
    {
        while(n>0)
        {
            s1.push(n);
            s2.push(L1);
            n--;
        }
        while(!s1.empty())
        {
            x=s2.top(); s2.pop();
            n=s1.top(); s1.pop();
            if(x==L1)
            {
                s1.push(n);
                s2.push(L2);
                n--;
                break;
            }
            if(x==L2)
            {
                cout<<n<<" ";
                if(n==tmp) flag=1;       //最后一次调用n时n==4,此时应该退出
            }
        }if(flag) break;
    }
}