/*********************************************************************
 *** Compile this program using the Visual C++ command line compiler
 *** by:
 ***   cl /EHsc fibonacci.cpp
 *********************************************************************/

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


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

unsigned int fib_nr(int n)
{
	if( n < 3 ) return 1;
	unsigned int fpp = 1, fp = 1, f;
	for(int i=3;i<=n;i++){
		f = fpp + fp;
		fpp = fp;
		fp = f;
	}
	return f;
}

void main(int argc, char *argv[])
{
	int n;

	n =  argc>1 ? atoi(argv[1]) : 1000;
	n = n ? n : 1000;

	DWORD runtime = GetTickCount();
	cout<<"Fibonacci("<<n<<") = "<<fib_r(n)<<" (by recursion)"<<endl;
	runtime = GetTickCount() - runtime;
	cout<<"Runtime is "<<runtime<<" msec\n";

	runtime = GetTickCount();
	cout<<"Fibonacci("<<n<<") = "<<fib_nr(n)<<endl;
	runtime = GetTickCount() - runtime;
	cout<<"Runtime is "<<runtime<<" msec\n";



	return;
}