First, a version of the code that will compile on a modern g++:
#include <iostream>
template<int N> struct fib {
static const int result = fib<N-1>::result + fib<N-2>::result;
};
template<> struct fib<0> {
static const int result = 0;
};
template<> struct fib<1> {
static const int result = 1;
};
int main(int ac, char *av[])
{
std::cout << "Fib(10) = " << fib<10>::result << std::endl;
return 0;
}
It might be worth exploring why exactly the above program is linear in compile time rather than exponential. After all, if the computation is being done at compile time, and the run-time of the algorithm is expected to be exponential, then compiling the program should be exponential, right? Let's take a look.
First, let's consider what fib(n) depends on, in this algorithm. Obviously, fib(10) (to continue with the example above) depends on fib(9) and fib(8). But fib(9) depends on fib(8) as well! (It also depends on fib(7)). Obviously, there's some repeated work here; in fact, the repeated work is the source of the expected exponential run-time. If, instead, we cached the value of fib for each n after the first time we computed it, we would only need to do n computations for fib(n), giving us a linear run-time (this type of algorithm is known as dynamic programming).
Now, let's examine what your C++ compiler does when faced with the above code. Firstly, fib is a struct (i.e., a type) parametrized over an integer N. Just like templates using type parameters, fib is code for which a certain detail is left open until the code is used; the only difference is that detail is a value instead of a type. When using such a template, you specify the value explicitly, and the resulting code gets instantiated. So in main(), when you access fib<10>::result, fib gets instantiated with the value 10. However, to do so, because of the way fib is defined, fib<9> and fib<8> must also be instantiated. Recall that fib<9> also needs fib<8>; but at this point, fib<8> has already been instantiated, so the compiler doesn't need to do any extra work, and just emits code to read fib<8>::result. This is exactly like caching the value of fib(n), like we discussed above! And thus compilation time is linear in n.
One final C++ detail that's worth exploring: how does the recursion stop? In a normal recursive function fib(n), you'd have some sort of conditional at the top that exited the recursion when presented with a base case. It turns out C++ templates have a little feature called partial specialization. The idea, going back to type templates, is that maybe you want your templated class or function to do something different for a particular type than the normal case. In the case of fib, we have it specialized for the value 0 and 1, for which result is not defined recursively, but rather initialized with a constant. Thus, when the compiler reaches fib<2> and has to access fib<1>::result and fib<0>::result, it just outputs code to access the constants we wrote in those specializations of fib. (ML hackers will notice that this looks a awful lot like pattern matching arguments).