How compile time recursion works?

Question

I found a code here Printing 1 to 1000 without loop or conditionals

Can someone please explain how compile time recursion works, couldn't find it in google

// compile time recursion
template<int N> void f1()
{ 
    f1<N-1>(); 
    cout << N << '\n'; 
}

template<> void f1<1>() 
{ 
    cout << 1 << '\n'; 
}


int main()
{
    f1<1000>();
}

Thank you!

Answer 1

It repeatedly instantiates the f1<N> template with decreasing values for N (f1<N>() calls f1<N-1> and so on). The explicit specialization for N==1 ends the recursion: as soon as N becomes 1, the compiler will pick the specialized function rather than the templated one.

f1<1000>() causes the compiler to instantiate f1<N> 999 times (not counting in the final call to f1<1>). This is the reason why it can take a while to compile code that makes heavy use of template meta-programming techniques.

The whole thing relies heavily on the compiler's optimization skills - ideally, it should remove the recursion (which only serves as hack to emulate a for loop using templates) completely.

Answer 2

It works conceptually almost the same way as runtime recursion. f1<1000> calls f1<999> and then prints out 1000. f1<999> calls f1<998> and then prints out 999, etc. Once it gets to 1 the template specialization acts as the base case to abort the recursion.