/*
* Name: Savio Alphonso
* Student Number: 100256601
* Course: CPSC 1160 - 001 | Assignment 3: Recursive vs Iterative
* Limitations:
*   - Program cannot handle text input -- it goes into an endless loop
*   - Program is limited to factorials up to 100 digits long
*   - Fibonacci Sequences are limited to the limit of a long long
* Sources:
*   - https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic
* Function:
*   - This program calculates n-th factorial/Fibonacci Sequence using recursive
*     and iterative methods.
*/

#include <iostream>

using namespace std;

const int DIGIT_LIMIT = 100; // maximum number of digits we can store in the array
const int BASE = 10; // the base we're currently working in


//Iterative way to find the n-th term in the Fibonacci Sequence.
// Parameters: n (Integer) - n-th value of Fibonacci Sequence to find
long long iterFibo(int n){
  long long temp; //temp variable
  long long prevFib = 0; // previous sequence number
  long long curFib = 1; // current sequence number

  if (n == 0 || n == 1) {
    return n; // if n is equal to 1 or 0 return 1 or 0 respectively
  }else{
    for (int i = 1; i < n; i++) {
      temp = curFib; // store the current value
      curFib += prevFib; //add the previous value to the current
      prevFib = temp; // set previous value
    }
  }

  return curFib;
}

// Recursive way of finding n-th term of the Fibonacci Sequence
// Parameters: Integer n - n-th term of the Sequence to find
long long recFibo(int n){
  if (n == 0 || n == 1) {
    return n; // if n is equal to 1 or 0 return 1 or 0 respectively
  }else{
    return recFibo(n-1) + recFibo(n-2); // recursive call.
  }
}



// Iterative way to find n-th term of a factorial.
// Since long long can only store 19 digits we need to store it the digits in an array
// Parameters: (Integer) n -  n-th term to find
void iterFact(int n){

  /*
  Since we want to display arbritary precise number we have store the number in
  an array, where each element is one digit, for our purposes we need to store up
  to 50!
  */

  int factorialLimit = n; // the factorial we want to find
  int digits[DIGIT_LIMIT] = {0}; //fill the arrays with zeros with size of the Limit
  int carry, placeVal; //carry variable and current place

  digits[DIGIT_LIMIT-1] = 1; //set the first factorial.
  placeVal = DIGIT_LIMIT - 1; //stores amount of digits

  for(int f = 1; f <= factorialLimit; f++){
    carry = 0;
    for(int d = 99; d >= placeVal; --d){
      digits[d] = (digits[d]*f) + carry; //find the factorial and the base
      carry = digits[d] / BASE; // calculate the carry
      digits[d] %= BASE; // store single digit in the array
    }

    //Handles carrying digits & calculating number of digits
    while(carry > 0) {
        if(placeVal >= DIGIT_LIMIT){
            cout << "overflow" <<endl;
        }

        placeVal--;
        digits[placeVal] = carry % BASE;
        carry /= BASE;
    }


  }
    //print without leading zero
     for (int i = placeVal; i < DIGIT_LIMIT; i++) {
      cout << digits[i];
    }

}

// Recursive way to find n-th term of a factorial.
// Since long long can only store 19 digits we need to store it the digits in an array
// Parameters: (Integer) n -  n-th term to find
void recFact(int digitArr[], int n){

  if (n == 0){
    return; // return nothing if n = 0, array take care of adding a zero.
  }


  //Similar to how the iterative precision works, but modified for recursive
  int carry = 0;
  for (int i=DIGIT_LIMIT-1; i>=0; --i){
      digitArr[i] = (digitArr[i] * n) + carry;
      carry = digitArr[i] / BASE;
      digitArr[i] %= BASE;
  }
  recFact(digitArr,n-1);
}

//Prints the recursive funtion array
//Parameters: Single Integer Array digitArr - array created by the recursive factorial function
void printRecFact(int digitArr[]){

  int firstNonZero = false;

  for (int i = 0; i < DIGIT_LIMIT; i++) {
   if (!firstNonZero && digitArr[i] != 0) { //skip printing until we find a non zero number
     firstNonZero = true;
   }

   if (firstNonZero) {
     cout << digitArr[i];
   }
  }

  fill(digitArr, digitArr+(DIGIT_LIMIT),0); // reset the array after printing
  digitArr[DIGIT_LIMIT - 1] = 1; // set first factorial value
}

int main() {
  int digits[DIGIT_LIMIT] = {0}; //set array to zero
  digits[DIGIT_LIMIT - 1] = 1; //set first factorial value


  char answer = 'Y';
  int n;
 do {
  cout << endl << endl;
  cout <<">===============( New RUN )===============<" <<endl;
  cout << "\nPlease enter an integer number: ";
  cin >> n;
  cout << endl;
  cout << "Iterative Factorial(" << n <<") is ";
  iterFact(n);
  cout << endl << "Recursive Factorial(" << n <<") is ";
  recFact(digits, n);
  printRecFact(digits);
  cout <<endl << "Iterative Fibonacci(" << n <<") is " << iterFibo(n) << endl;
  cout << "Recursive Fibonacci(" << n <<") is " << recFibo(n) << endl << endl;
  cout << "Do you want to continue? (Y/N)";
  cin >> answer;
  digits[DIGIT_LIMIT] = {0};
 } while (toupper(answer) == 'Y');
  cout << "The Program has ended gracefully!" ;
  return 0;
}