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).