cpp-templatesC++ template system is Turing-complete<br>2026-05<br>A recursive Fibonacci number implementation in C++ is straightforward:

int fib(int n) {<br>if (n 1) return n;<br>return fib(n - 1) + fib(n - 2);

int main() {<br>int n = 10;<br>std::cout "The Fibonacci number at position " " is: " fib(n) return 0;

C++ templates let us write "generic" code, based on some parameters, at compile-time. The C++ compiler then generates code for us based on each type/value instantiation. It turns out a Fibonacci number implementation in C++ templates is also possible:

template int N><br>struct Fib {<br>static constexpr int value =<br>Fib-1>::value + Fib-2>::value;<br>};

template <><br>struct Fib0> {<br>static constexpr int value = 0;<br>};

template <><br>struct Fib1> {<br>static constexpr int value = 1;<br>};

int main() {<br>constexpr int n = 10;<br>std::cout "The Fib number at position " " is: " ::value return 0;

This generates the same output! In the implementation using templates, the only meaningful work done at runtime is printing to stdout. All the computation is done at compile-time:

The C++ compiler evaluates a recursive function call graph for us. Upon encountering Fib, it pattern-matches against all known template specializations, namely for Fib and Fib.

The two explicit template specializations Fib and Fib handle the base case.

The static constexpr keywords indicate that values can be evaluated at compile-time. Specifically, the compiler generates (in this case) 11 unique class definitions Fib, ..., Fib.

Finally, as n approaches a limit (configurable via -ftemplate-depth), compilation will fail with something like fatal error: recursive template instantiation exceeded maximum depth.

Template specialization is conditional branching, and template instantiation serves as a key-value store. Here's a more complete demonstration that C++ templates are Turing-complete.