＜栈模拟递归＞

1.求解斐波那契数列第n项值

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 3e5 +5;
struct Node {
    
    ll x , res , state;
    // x 代表输入参数
    // res 存储当前答案
    // state 代表递归阶段
};
ll f (ll x){
    
    stack<Node> s;
    s.push({
    x , 0 , 0});
    ll ret = 0;
    while(s.size()){
    
        Node u = s.top();
        s.pop();
        // 递归出口
        if (u.x == 0 || u.x == 1) {
    
            ret = 1;
            continue;
        }
        if (u.state == 0){
     // 递1阶段
            s.push({
    u.x , 0 , 1}); // 保存现场，等待递2阶段
            s.push({
    u.x - 1 , 0});
        }else if (u.state == 1){
     // 递2阶段
            s.push({
    u.x , ret , 2});
            s.push({
    u.x - 2 , 0 , 0});
        }else{
    
            ret += u.res;
        }
    }
    return ret;
}
int main()
{
    
    int x;
    while (cin >> x) cout << f(x) << endl;
    return 0;
}

2.求全排列

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 3e5 +5;
struct Node {
    
    int state , ptr;
    // state 代表递归阶段
    // ptr 代表循环变量所指向的位置
};
void f (ll n , vector<string> &res){
    
    stack<Node> s;
    s.push({
    1 , 1});
    string a;
    for (int i = 1 ; i <= n ; i++) a += to_string(i);
    while(s.size()){
    
        Node u = s.top();
        s.pop();
        if (u.state == n + 1) {
    
            res.push_back(a);
            continue;
        }
        if (u.ptr - 1 > u.state)
            swap(a[u.state - 1] , a[u.ptr - 1 - 1]);
        swap(a[u.state - 1] , a[u.ptr - 1]);
        if (u.ptr + 1 <= n)
            s.push({
    u.state , u.ptr + 1});
        s.push({
    u.state + 1 , u.state + 1});
    }
    return ;
}
int main()
{
    
    int x;
    while (cin >> x) {
    
        vector<string> res;
        f(x , res);
        cout << res.size() << endl;
    }
    return 0;
}