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!

Actually there is a trick, the specialization is a conditional, though there is no `if` keyword... — Matthieu M., Mar 11 '11 at 18:20
Is there a rule of thumb about much faster this is than run time recursion? — David Doria, Jan 29 '12 at 20:26
Whats the benefit of using this in place of regular recursion? — zzzzz, Jun 10 '13 at 08:03

score 12 · Accepted Answer · edited Mar 12 '11 at 21:18

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.

score 2 · Answer 2 · answered Mar 11 '11 at 14:32

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.

answered Mar 11 '11 at 14:32

Mark B

95,107
10
109
188

why does it print from 0 to 1000 and not from 1000 to 0? – VextoR Mar 11 '11 at 14:43
1

@VextoR: That's because it first calls f1, then prints. – sharptooth Mar 11 '11 at 14:46
1

@VextoR because it's outputting `N` to the console AFTER instantiating the next template. – Maxpm Mar 11 '11 at 14:47
@sharptooth == 999? Should it print "999" ? – VextoR Mar 11 '11 at 14:48
@VextoR: No, it first calls `f1<999>()`, then prints 1000. – sharptooth Mar 11 '11 at 14:50

score 2 · Answer 3 · answered Mar 11 '11 at 14:45

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.

score 1 · Answer 4 · answered Mar 11 '11 at 14:33

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.

score 1 · Answer 5 · answered Mar 11 '11 at 14:47

1

You have factorial calculation explained here.

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

answered Mar 11 '11 at 14:47

BЈовић

62,405
41
173
273

How compile time recursion works?

5 Answers5

Linked