/* Dan Roche TimeFib.cc
 * This shows how to use the StopWatch class to find timing information on two
 * versions of the fibonacci function
 */

#include <iostream>
#include "StopWatch.h" // You must include this file for the StopWatch to work

using std::cout;
using std::endl;

// Prototypes - don't worry too much about the actual function definitions.
int fibRecursive( int n );
int fibIterative( int n );

int main() {
	// Here are two variables to control the timing calculations. For your
	// program, these will be input from the user.
	int nloops = 50000; // The number of times to loop
	int n = 12; // Which term in the Fibonacci series to calculate

	StopWatch s; // Create a StopWatch object
	s.reset(); // Reset the stopwatch to zero
	s.start(); // Start the stopwatch

	for( int i = 0; i < nloops; ++i ) {
		fibRecursive(n);
	}

	s.stop(); // Stop the stopwatch
	int recTime = s.readValue(); // Record the timing.

	// Now repeat all that for the other function.

	s.reset();
	s.start();

	for( int i = 0; i < nloops; ++i ) {
		fibIterative(n);
	}

	s.stop();
	int itTime = s.readValue();

	// Print out the results
	cout << "Time for recursive version: " << recTime << endl;
	cout << "Time for iterative version: " << itTime << endl;

	return 0;
}

// This function uses recursion to compute the nth term of the Fibonacci
// sequence.
// The input, n, must be a nonnegative integer.
int fibRecursive( int n ) {
	if( n == 0 || n == 1 ) return 1;
	else return (fibRecursive( n - 1 ) + fibRecursive( n - 2 ));
}

// This function uses a for loop to compute the nth term of the Fibonacci
// sequence.
// The input, n, must be a nonnegative integer.
int fibIterative( int n ) {
	int current = 1, previous = 1;
	int temp;
	if( n == 0 || n == 1 ) return 1;
	for( int i = 2; i <= n; ++i ) {
		temp = current;
		current = current + previous;
		previous = temp;
	}
	return current;
}