This Fibonacci implementation is part of a compare-and-contrast with this other Fibonacci implementation: https://gist.github.com/kinchungwong/7701952 Technically speaking, this version (300 lines of commented code) has 46 essential semicolons for its implementation part (excluding the main function), while the other implementation (34 lines of …

Cpp_Fibonacci_Working.cpp

// -------------------------------------------------------
//
//  A fool's journey into C++ template metaprogramming, 
//   --- the non-shortest-path version.
//
// -------------------------------------------------------
//
//  Warning: This is a recursively cursed, non-terminating
//  path. See Warning.
//
// -------------------------------------------------------

#include <iostream>
using namespace std;

// -------------------------------------------------------
//  A curious trapdoor utilized for its SFINAE quality, 
//  which is used in the construction of the Eval 
//  metafunction below.
// -------------------------------------------------------

template <typename>
struct Void
{
	typedef void type;
};

// -------------------------------------------------------
//  Eval metafunction. 
//  Responsible for the wrapping and unwrapping 
// -------------------------------------------------------

template <class C, typename = void>
struct Eval
{
	typedef C type;
};

template <class C>
struct Eval<C, typename Void<typename C::type>::type>
{
	typedef typename C::type type;
};

// Instead of having an unspecified prototype, 
// each metafunction agrees to treat every input argument as metafunctions 
// themselves if there is no further clue (specialization matches) for 
// their handling.

// ---------------------------------------
//  Add metafunction
// ---------------------------------------

template <class First, class Second> 
struct Add
{
	// Without further knowledge of First and Second, both arguments
	// are evaluated. After that, we define "the four members":
	//   1. typedef type;
	//   2. typedef value_type;
	//   3. static const value_type value;
	//   4. value_type operator()() const;
	//	
	typedef typename Add<
		typename Eval<First>::type, 
		typename Eval<Second>::type
		>::type type;
	typedef int value_type;
	static const int value = type::value;
	int operator()() const { return value; }
};

template <int First, int Second>
struct Add<
	std::integral_constant<int, First>, 
	std::integral_constant<int, Second>>
	: std::integral_constant<int, (First + Second)>
{
	// Inherited "the four members" from std::integral_constant
};

// ---------------------------------------
//  Subtract metafunction
// ---------------------------------------

template <class First, class Second>
struct Subtract
{
	// Without further knowledge of First and Second, both arguments
	// are evaluated. After that, we define "the four members":
	//   1. typedef type;
	//   2. typedef value_type;
	//   3. static const value_type value;
	//   4. value_type operator()() const;
	//	
	typedef typename Subtract<
		typename Eval<First>::type,
		typename Eval<Second>::type
		>::type type;
	typedef int value_type;
	static const int value = type::value;
	int operator()() const { return value; }
};

template <int First, int Second>
struct Subtract<
	std::integral_constant<int, First>,
	std::integral_constant<int, Second>>
	: std::integral_constant<int, (First - Second)>
{
	// Inherited "the four members" from std::integral_constant
};

// ---------------------------------------
//  Equals metafunction
// ---------------------------------------

template <class First, class Second>
struct Equals
{
	// Without further knowledge of First and Second, both arguments
	// are evaluated. After that, we define "the four members":
	//   1. typedef type;
	//   2. typedef value_type;
	//   3. static const value_type value;
	//   4. value_type operator()() const;
	//	
	typedef typename Equals<
		typename Eval<First>::type,
		typename Eval<Second>::type
		>::type type;
	typedef bool value_type;
	static const bool value = type::value;
	bool operator()() const { return value; }
};

template <class First>
struct Equals<
	First, 
	First>
	: std::true_type
{
	// Inherited "the four members" from std::true_type
	// Equality is deduced by type, without evaluation.
};

template <int First, int Second>
struct Equals<
	std::integral_constant<int, First>, 
	std::integral_constant<int, Second>>
	: std::false_type
{
	// Inherited "the four members" from std::false_type
};

template <int First>
struct Equals<
	std::integral_constant<int, First>, 
	std::integral_constant<int, First>>
	: std::true_type
{
	// Inherited "the four members" from std::true_type
};

// ---------------------------------------
//  Less metafunction
// ---------------------------------------

template <class First, class Second>
struct Less
{
	// Without further knowledge of First and Second, both arguments
	// are evaluated. After that, we define "the four members":
	//   1. typedef type;
	//   2. typedef value_type;
	//   3. static const value_type value;
	//   4. value_type operator()() const;
	//	
	typedef typename Less<
		typename Eval<First>::type,
		typename Eval<Second>::type
		>::type type;
	typedef bool value_type;
	static const bool value = type::value;
	bool operator() () const { return value; }
};

template <class First>
struct Less<First, First>
	: std::false_type
{
	// Inherited "the four members" from std::false_type
	// Two equal values cannot be any less than the other.
};

template <int First, int Second>
struct Less<
	std::integral_constant<int, First>,
	std::integral_constant<int, Second>>
	: std::integral_constant<bool, (First < Second)>
{
	// Inherited "the four members" from std::integral_constant
};

template <int First>
struct Less<
	std::integral_constant<int, First>,
	std::integral_constant<int, First>>
	: std::false_type
{
	// Inherited from std::false_type
	// Two equal values cannot be any less than the other.
};

// ---------------------------------------
//  Conditional evaluation metafunction
// ---------------------------------------

template <bool Cond, class EvalIfTrue, class EvalIfFalse>
struct ConditionalEval;

template <class EvalIfTrue, class EvalIfFalse>
struct ConditionalEval<false, EvalIfTrue, EvalIfFalse>
{
	typedef typename EvalIfFalse::type type;
};

template <class EvalIfTrue, class EvalIfFalse>
struct ConditionalEval<true, EvalIfTrue, EvalIfFalse>
{
	typedef typename EvalIfTrue::type type;
};

// ---------------------------------------
//  Recursive Fibonacci metafunction
// ---------------------------------------

template <class CIndex>
struct Fibonacci
{
	struct small_numbers
	{
		typedef std::integral_constant<int, 0> N0;
		typedef std::integral_constant<int, 1> N1;
		typedef std::integral_constant<int, 2> N2;
		typedef std::integral_constant<int, 42> Nuniverse;
	};
	
	struct lazy_recursion
	{
		typedef Eval<
			Fibonacci<
				typename Subtract<
					CIndex, 
					typename small_numbers::N1
				>::type
			>
		> FibonacciMinusOne;
		
		typedef Eval<
			Fibonacci<
				typename Subtract<
					CIndex, 
					typename small_numbers::N2
				>::type
			>
		> FibonacciMinusTwo;
	};
	
	typedef typename ConditionalEval<
		Less<
			CIndex, 
			typename small_numbers::N2
		>::value,
		typename small_numbers::N1,
		Add<
			typename lazy_recursion::FibonacciMinusOne, 
			typename lazy_recursion::FibonacciMinusTwo
		>
	>::type type;
};

// ---------------------------------------
//  main(), the only "non-meta" function
// ---------------------------------------

int main() 
{
	typedef std::integral_constant<int, 0> N0;
	typedef std::integral_constant<int, 1> N1;
	typedef std::integral_constant<int, 2> N2;
	typedef std::integral_constant<int, 3> N3;
	typedef std::integral_constant<int, 4> N4;
	typedef std::integral_constant<int, 5> N5;
	std::cout << "N0 gives: " << Fibonacci<N0>::type::value << std::endl;
	std::cout << "N1 gives: " << Fibonacci<N1>::type::value << std::endl;
	std::cout << "N2 gives: " << Fibonacci<N2>::type::value << std::endl;
	std::cout << "N3 gives: " << Fibonacci<N3>::type::value << std::endl;
	std::cout << "N4 gives: " << Fibonacci<N4>::type::value << std::endl;
	std::cout << "N5 gives: " << Fibonacci<N5>::type::value << std::endl;
	return 0;
}