// To compile this C++ program, open a terminal window and type
// g++ fibonacci.C -o fibonacci
// To run it, type
// ./fibonacci <number>
// where <number> is a number, e.g. 45.
// Have fun!

#include <iostream> // std::cout, std::cerr, std::endl
#include <sstream> // stringstream
#include <vector> // vector<>

long int fibo_full_recursion( long int n )
{
	if ( n == 0 ) return 0;
	if ( n == 1 ) return 1;
	return fibo_full_recursion(n-1) + fibo_full_recursion(n-2);
}

long int fibo_dyn_prog( long int n )
{
	if ( n == 0 ) return 0;
	if ( n == 1 ) return 1;

	std::vector<long int> fibo_vec;
	fibo_vec.resize(n+1);
	fibo_vec[0] = 0;
	fibo_vec[1] = 1;
	for ( int i = 2; i <= n; ++i )
	{
		fibo_vec[i] = fibo_vec[i-1] + fibo_vec[i-2];
	}
	return fibo_vec[n];
}

int main ( int argc, char ** argv )
{
	if ( argc != 2 )
	{
		std::cerr <<
			"This program computes Fibonacci numbers.\n"
			"Usage: " << argv[0] << " <number>" << std::endl;
		return 1;
	}

	// read the command line argument
	std::stringstream param(argv[1]);
	int n = -1;
	param >> n;
	if ( !param || n < 0 )
	{
		std::cerr << "Invalid number: " << argv[1] << std::endl;
		return 1;
	}

	// compute F[n] both ways
	std::cout << "Computing F[" << n << "]" << std::endl;
	std::cout << "Using fibo_dyn_prog: " << fibo_dyn_prog(n) << std::endl;
	std::cout << "Using fibo_full_recursion: " << fibo_full_recursion(n) << std::endl;

	return 0;
}