fibonacci.cpp

/*
The teacher asked us to use the stack to turn the recursive algorithm into non-recursive, so I wrote this.🤣
#1 https://gist.github.com/zwongeer/1def202a5ab8bb44b25c05f470681621
#2
*/
#include <algorithm>
#include <iostream>
#include <memory>
#include <cstdlib>
#include <stack>
using std::cout, std::cin, std::endl;

int fib(int n) {
    if (n <= 1) return n;
    int v1 = fib(n - 1);
    int v2 = fib(n - 2);
    return v1 + v2;
}

int fib_ng(int n) {
    enum struct jmp_flag {NONE, FIRST, SECOND};
    struct local_var {int v1; int v2;};
    std::stack<int> args_stack;
    std::stack<jmp_flag> status_stack;
    std::stack<int> rets_stack;
    std::stack<local_var> local_stack;

    args_stack.push(n);
    status_stack.push(jmp_flag::NONE);
    while (!args_stack.empty()) {
    jmp_flag jflag = status_stack.top();
    status_stack.pop();
    switch (jflag) {
        case jmp_flag::NONE:
        local_stack.emplace();
        rets_stack.emplace();
        if (args_stack.top() <= 1) {
            rets_stack.top() = args_stack.top();
            break;
        }

        args_stack.push(args_stack.top() - 1);
        status_stack.push(jmp_flag::FIRST);
        status_stack.push(jmp_flag::NONE);
        continue;
        case jmp_flag::FIRST:
        local_stack.top().v1 = rets_stack.top();
        rets_stack.pop();

        args_stack.push(args_stack.top() - 2);
        status_stack.push(jmp_flag::SECOND);
        status_stack.push(jmp_flag::NONE);
        continue;
        case jmp_flag::SECOND:
        local_stack.top().v2 = rets_stack.top();
        rets_stack.pop();

        rets_stack.top() = local_stack.top().v1 + local_stack.top().v2;
    }
    args_stack.pop();
    local_stack.pop();
    }
    return rets_stack.top();
}

int main(int argc, char const *argv[])
{
    for (int i = 1; i < 10; ++i)
        cout << fib_ng(i) << " " << endl;
    return 0;
}