// fibo5.cpp
// Glenn G. Chappell
// 7 Apr 2008
//
// For CS 311 Spring 2008
// Computing Fibonacci Numbers
// Version #5: Recursion Eliminated
//
// This program is based on fibo1.cpp.
// Recursion has been eliminated using the "brute force"
//  technique described in class.

#include <iostream>
using std::cout;
using std::endl;
#include <stack>  // for std::stack


/*
Original function fibo, from fibo1.cpp:

int fibo(int n)
{
    // BASE CASE
    if (n <= 1)
        return n;

    // RECURSIVE CASE
    return fibo(n-2) + fibo(n-1);
}

Modified version used as the basis of this code:

int fibo(int n)
{
    int v1, v2;

    // Base Case
    if (n <= 1)
        return n;

    // Recursive call #1
    v1 = fibo(n-2);

    // Recursive call #2
    v2 = fibo(n-1);

    // Return the result
    return v1 + v2;
}
*/


// struct FiboStackFrame
// "Stack frame" - holds local values for function fibo.
// In a structure so that they can be saved on a stack.
struct FiboStackFrame {
    int n;            // Parameter
    int v1;           // Result of recursive call #1
    int v2;           // Result of recursive call #2
    int returnValue;  // Value to return
    int returnAddr;   // Return address:
                      //     0: outside world (return from function)
                      //     1: recursive call #1 (return to label1)
                      //     2: recursive call #2 (return to label2)
};


// fibo
// Given n, returns F(n) (the nth Fibonacci number).
// F(0) = 0. F(1) = 1. For n >= 2, F(n) = F(n-2) + F(n-1).
// Pre:
//     n >= 0.
//     F(n) is a valid int value.
// Note: For 32-bit signed int's, preconditions hold for 0 <= n <= 46.
// Post:
//     Return value is F(n).
// May throw std:bad_alloc if Stack space runs out.
// Strong Guarantee
int fibo(int n)
{
    // *************************************
    // ORIGINAL CODE:
    // int fibo(int n)
    // {
    //     int v1, v2;
    // *************************************

    // Local variables
    int tmp;  // Temp value - holds an int during stack op's
    std::stack<FiboStackFrame> s;
              // Stack, used to eliminate recursion
              // Top of stack holds current local variables
              //  and place for return value

    // Set up stack frame.
    s.push(FiboStackFrame());  // Make new stack frame
    s.top().n = n;             // Set parameter
    s.top().returnAddr = 0;    // Set return address (called by outside world)

    // *************************************
    // BEGIN LOOP
    // while (true) loop used for recursion
    // elimination.
    // *************************************
    while (true)
    {

        // *************************************
        // ORIGINAL CODE:
        // // Base Case
        // if (n <= 1)
        //     return n;
        // *************************************
        if (s.top().n <= 1)
        {
            // Do "return n;"
            s.top().returnValue = s.top().n;

            if (s.top().returnAddr == 1)       // Back to recursive call #1
                goto label1;
            else if (s.top().returnAddr == 2)  // Back to recursive call #2
                goto label2;
            else                               // Back to outside world
            {
                tmp = s.top().returnValue;
                s.pop();
                return tmp;
            }
        }

        // *************************************
        // ORIGINAL CODE:
        // // Recursive call #1
        // v1 = fibo(n-2);
        // *************************************
        tmp = s.top().n - 2;
        s.push(FiboStackFrame());  // Make new stack frame
        s.top().n = tmp;           // Set parameter
        s.top().returnAddr = 1;    // Set return address (recursive call #1)
        continue;                  // Do "recursive call"
label1:                            // Place to return to
        tmp = s.top().returnValue;
        s.pop();
        s.top().v1 = tmp;          // Put returned value in v1

        // *************************************
        // ORIGINAL CODE:
        // // Recursive call #2
        // v2 = fibo(n-1);
        // *************************************
        tmp = s.top().n - 1;
        s.push(FiboStackFrame());  // Make new stack frame
        s.top().n = tmp;           // Set parameter
        s.top().returnAddr = 2;    // Set return address (recursive call #2)
        continue;                  // Do "recursive call"
label2:                            // Place to return to
        tmp = s.top().returnValue;
        s.pop();
        s.top().v2 = tmp;          // Put returned value in v2

        // *************************************
        // ORIGINAL CODE:
        // // Return the result
        // return v1 + v2;
        // *************************************
        s.top().returnValue = s.top().v1 + s.top().v2;

        if (s.top().returnAddr == 1)       // Back to recursive call #1
            goto label1;
        else if (s.top().returnAddr == 2)  // Back to recursive call #2
            goto label2;
        else                               // Back to outside world
        {
            tmp = s.top().returnValue;
            s.pop();
            return tmp;
        }

    // *************************************
    // END LOOP
    // while (true) loop used for recursion
    // elimination.
    // *************************************
    }
}


// main
// From fibo1.cpp
int main()
{
    cout << "Fibonacci Numbers" << endl;
    cout << endl;
    for (int i = 0; i <= 46; ++i)
    {
        cout << i << ": " << fibo(i) << endl;
    }
}