Fibonacci using explict stack.

stack_fibonacci.cpp

int fib(int n) {
    // Init:
    if (n <= 2)  {
        return 1;
    }
    int a = fib(n - 1);
    // Resume 1:
    int b = fib(n - 2);
    // Resume 2:
    return a + b;
}

struct Params {
    int n;
};

struct Variables {
    int a;
    int b;
};

struct Result {
    int returnValue;
};

enum Op {
    InitialCall,
    Resume1,
    Resume2
};

struct Frame {
    Op op;
    Params params;
    Variables variables;
};

int fib2(int n) {
    stack<Frame> s;
    stack<Result> r;
    s.push({
        InitialCall,
        { n },
        { 0, 0 },
    });
    while (!s.empty()) {
        auto frame = s.top();
        s.pop();
        int localN = frame.params.n;
        int localA = frame.variables.a;
        int localB = frame.variables.b;
        switch (frame.op) {
            case Op::InitialCall: {
                if (localN <= 2) {
                    r.push({ 1 });
                    break;
                }
                s.push({ Resume1, { localN }, { 0, 0 } });
                s.push({ InitialCall, { localN - 1 }, { 0, 0 } });
                break;
            }
            case Op::Resume1: {
                auto result = r.top().returnValue;
                r.pop();
                s.push({ Resume2, { localN }, { result, 0 } });
                s.push({ InitialCall, { localN - 2 }, { 0, 0 } });
                break;
            }
            case Op::Resume2: {
                auto result = r.top().returnValue;
                r.push({ localA + result });
                break;
            }
        }
    }
    return r.top().returnValue;
}