/* 
 * Michael Gousie
 * COMP 318  Spring 2026
 * fib.cpp
 *
 * Display the nth Fibonacci number.
 *
 * F(1) = 1 is the first one by this definition; F(0) is 0
 * n:      1 2 3 4 5 6  7  8  9 10
 * fib(n): 1 1 2 3 5 8 13 21 34 55
 *
 * This program shows the recursive and iterative implementations.
 * Each displays the number of ops required and the total time.
 */


#include<iostream>
#include<time.h>
using namespace std;

double countr = 0;  // count of recursive ops
double countn = 0;  // count of iterative ops

float fibr (float x) {
// recursive fibonacci sequence
   if (x == 0) {
      countr = countr + 1;
      return 0;
   }
   else if (x == 1) {
      countr = countr + 1;
      return 1;
   }
   else {
      countr = countr + 1;
      return (fibr (x-1) + fibr (x-2));
   }
}

float fibn (float x, double &durationn) {
// nonrecursive version
   float one, two, three;
   int i;
   double start, stop;

   if (x == 0) {
      countn = countn + 1;
      return 0;
   }
   else if (x == 1) {
      countn = countn + 1;
      return 1;
   }
   else {
      start = (double) clock();
      one = 0;
      two = 1;
      for (i = 2; i <= x; i++) {
         countn = countn + 1;
         three = one + two;
         one = two;
         two = three;
      }
      stop = (double) clock();
      durationn = stop - start;
      return three;
   }
}



int main () {
   int n;
   float result;
   double start, stop, durationr, durationn;

   cout << endl << "Input n: ";
   cin >> n;

   cout << endl << "Iterative version~~~" << endl;
   cout << "The " << n << "th fibonacci number is: ";
   cout << fibn (n, durationn) << endl;
   cout << "Count: " << countn << ";  Total time (sec): ";
   cout << durationn/CLOCKS_PER_SEC << endl;

   cout << endl << "Recursive version~~~" << endl;
   cout << "The " << n << "th fibonacci number is: ";
   start = (double) clock ();
   result = fibr (n);
   stop = (double) clock ();
   durationr = (stop - start) / CLOCKS_PER_SEC;
   cout << result << endl;
   cout << "Count: " << countr << ";  Total time (sec): " ;
   cout << durationr << endl;
   return 0;
}