#include <iostream>

namespace Details
{
template < typename F >
struct has_next
{
	typedef char yes[1];
	typedef char no[2];
	
	template < typename C >
	static yes& test(typename C::next *);
	
	template < typename C >
	static no& test(...);
	
	enum { value = sizeof(test<F>(0)) == sizeof(yes) };
	typedef has_next< F > type;
};

template < unsigned int n__ >
struct Fibonacci_
{
	enum { value = Fibonacci_< n__ - 1 >::value + Fibonacci_< n__ - 2 >::value };
	typedef Fibonacci_< n__ - 1 > next;
	typedef Fibonacci_< n__ > type;
};

template<>
struct Fibonacci_<1>
{
	enum { value = 1 };
	typedef Fibonacci_< 1 > type;
	typedef Fibonacci_< 0 > next;
};

template <>
struct Fibonacci_<0>
{
	typedef Fibonacci_< 0 > type;
	enum { value = 0 };
};

template < typename F, bool has_next__ >
struct Filler_
{
	static void fill(unsigned int *a)
	{
		*a = F::value;
		Filler_< typename F::next, has_next< typename F::next >::value >::fill(++a);
	}
};

template < typename F >
struct Filler_< F, false >
{
	static void fill(unsigned int *a)
	{
		*a = F::value;
	}
};

// based on idea by Luc Danton described here: http://chat.stackoverflow.com/transcript/message/740324#740324
// modified to use SFINAE and a class to implement the guts (so partial specialization will work)
template < typename F >
void fill(unsigned int *a)
{
	Filler_< F, has_next< F >::value >::fill(a);
}
}

template< unsigned int max__ = 20 >
unsigned int fibonacci(unsigned int n)
{
	static unsigned int results__[max__ + 1];
	static bool initialized__ = false;
	if (!initialized__)
	{
		Details::fill< Details::Fibonacci_< max__ > >(results__);
		initialized__ = true;
	}
	if (n <= max__)
	{
		return results__[max__ - n];
	}
	else throw "something more eloquent here";
}

int main()
{
	using namespace std;
	
	static const unsigned int max__ = 20;

	for (unsigned int i(0); i <= max__; ++i)	
		cout << fibonacci< max__ >(i) << '\n';
}