/* Lecture code 17.2
 *
 * Using template metaprogramming (TMP) to compute Fibonacci numbers
 * at compile-time.  There's also a recursive implementation available that
 * highlights how you can compute the same function at runtime.  Play around
 * with this code to see what you can come up with!
 */

#include <iostream>
using namespace std;

/* A template metaprogram to compute Fibonacci numbers.
 * Recursive case: Fib(n) = Fib(n - 1) + Fib(n - 2)
 */
template <int n> struct Fibonacci
{
	static const int result = Fibonacci<n - 1>::result + Fibonacci<n - 2>::result;
};

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

template <> struct Fibonacci<1>
{
	static const int result = 1;
};

/* A recursive function to compute Fibonacci numbers, for comparison. */
int FibRec(int n)
{
	if(n <= 1) return n;
	return FibRec(n - 1) + FibRec(n - 2);
}

/* Compute the 40th Fibonacci number in two ways - first using TMP,
 * which is instantaneous at runtime, and the second using recursion,
 * which takes quite some time to finish!
 */
int main()
{
	cout << Fibonacci<40>::result << endl;
	cout << FibRec(40) << endl;
	return 0;
}