栈模拟递归求阶乘问题

#include<iostream>
#include<stack>
using namespace std;
 
typedef struct{
    int n;//保存n值
    int f;//保存f(x)值
    int flag;//标记当前递归层是否可求出结果(1为已知，0为未知)
}fst;
 
int fun(int n){
    fst e,e1,e2;
    stack<fst>st;
    e.n=n;
    e.flag=0;
    st.push(e);//f(n)入栈
    while(!st.empty()){
        if(st.top().flag==0)//当前栈顶元素值未知时
        {
            if(st.top().n==1)//当前栈顶元素为f(1)时
            {
                st.top().f=1;
                st.top().flag=1;
            }
            else
            {
                e1.n=st.top().n-1;
                e1.flag=0;
                st.push(e1);//f(n-1)入栈
            }
        }
        else
        {
            e2=st.top();
            st.pop();//退栈
            st.top().f=st.top().n*e2.f;//f(n)=f(n-1)*n
            st.top().flag=1;
        }
        if(st.size()==1&&st.top().flag==1)
            break;
    }
    return(st.top().f);
}
 
int main(){
    int n;
    cout<<"请输入n的值:";
    cin>>n;
    cout<<n<<"的阶乘为"<<fun(n);
}

图1

-------该算法摘自《算法设计与分析(第2版)》