// Course:            CS 12

// Lecture Section:   1
// Lab Section:       21
// Assignment #:      In-lab exercise 2

// First Name:        Wagner
// Last Name:         Truppel
// ID Number:         12-345-678
// Email address:     wagner@cs.ucr.edu

// =======================================================================

#include <iostream>
#include <time.h>

const int MAX_N = 50;

const int N_WIDTH = 5;
const int LARGE_WIDTH = 12;

int fibo_rec = 1, fibo_iter = 1;
double elapsed_rec = 0, elapsed_iter = 0;

int FiboRec(const unsigned int n);
int FiboIter(const unsigned int n);

void PrintHeader();
void PrintOutput(const unsigned int n);

int main ()
{
    std::cout.setf(std::ios::fixed);
    std::cout.precision(0);
    
    PrintHeader();
    
    clock_t start;
    clock_t finish;
        
    start = clock();
    finish = clock();
    double delay = (double)(finish - start);
        
    for (int n = 1; n <= MAX_N; n++)
    {
        start = clock();
        fibo_iter = FiboIter(n);
        finish = clock();
        
        elapsed_iter = (double)(finish - start);
        elapsed_iter -= delay;
        
        start = clock();
        fibo_rec = FiboRec(n);
        finish = clock();
        
        elapsed_rec = (double)(finish - start);
        elapsed_rec -= delay;
        
        PrintOutput(n);
    }
    
    return 0;
}

void PrintHeader()
{
    std::cout.width(N_WIDTH);
    std::cout << "n" << " ";
    
    std::cout.width(LARGE_WIDTH);
    std::cout << "F(n) iter" << " ";
    
    std::cout.width(LARGE_WIDTH);
    std::cout << "time (iter)" << " ";
    
    std::cout.width(LARGE_WIDTH);
    std::cout << "F(n) rec" << " ";
    
    std::cout.width(LARGE_WIDTH);
    std::cout << "time (rec)" << std::endl;
}

void PrintOutput(const unsigned int n)
{
    std::cout.width(N_WIDTH);
    std::cout << n << " ";
    
    std::cout.width(LARGE_WIDTH);
    std::cout << fibo_iter << " ";
    
    std::cout.width(LARGE_WIDTH);
    std::cout << elapsed_iter << " ";
    
    std::cout.width(LARGE_WIDTH);
    std::cout << fibo_rec << " ";
    
    std::cout.width(LARGE_WIDTH);
    std::cout << elapsed_rec << std::endl;
}

int FiboRec(const unsigned int n)
{
    if (n < 3)
        return 1;
    else
        return FiboRec(n-1) + FiboRec(n-2);
}

int FiboIter(const unsigned int n)
{
    if (n < 3)
        return 1;
    else
    {
        int fn_minus_1 = 1;
        int fn_minus_2 = 1;
        int result = 0;
        
        for (unsigned int i = 3; i <= n; i++)
        {
            result = fn_minus_1 + fn_minus_2;
            fn_minus_1 = fn_minus_2;
            fn_minus_2 = result;
        }
        
        return result;
    }
}