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

Simple enough, each template instanciation create a new function with the changed parameter. Like if you defined: f1_1000(), f1_999() and so on.

Each function call the function with 1 less in it's name. As there is a different template, not recursive, to define f1_1() we also have a stop case.

Answer 2

This is not guaranteed to be pure compile-time recursion. The compiler will have to instantiate function f1() for all parameters value from 2 to 1000 and they will call each other.

Then the compiler might see that those calls can be just turned into a sequence of cout << ... statements. Maybe it eliminates calls, maybe not - this is up to the compiler. From the point of C++ this is a chain of function calls and the compiler can do whatever as long as it doesn't alter behavior.

Answer 3

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.

Answer 4

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 5

You have factorial calculation explained here.

btw that a note that your function doesn't work for negative numbers.