/* Lecture Code 8.3
 *
 * Advanced C++: Template Metaprogramming to compute Fibonacci numbers.
 */

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <sstream>
using namespace std;

/* Normal case: F(n) = F(n-1) + F(n-2) */
template<int myValue>
struct Fib
{
	static const int result = Fib<myValue - 1>::result + Fib<myValue - 2>::result;
};

/* Base case: F(1) = 1 */
template<>
struct Fib<1>
{
	static const int result = 1;
};

/* Base case: F(0) = 1 */
template<>
struct Fib<0>
{
	static const int result = 0;
};
 
/* A regular C++ function, which is dwarfed in speed. */
int FibFn(int value)
{
	if(value < 2)
		return value;
	return FibFn(value - 1) + FibFn(value - 2);
}

int main()
{
	cout << Fib<40>::result << endl;
	cout << FibFn(40) << endl;
	return 0;
}