Visual C++ Tail Call Optimization
c++, tail-call, tail-call-optimization, tail-recursion, visual-studio-2010
Solution
I don't use the MS compilers, but GCC can certainly do tail-recursion optimisation for templates. Given this function:
template <typename T>
T f( T t ) {
cout << t << endl;
if ( t == 0 ) {
return t;
}
return f( t - 1 );
}
The code produced is:
5 T f( T t ) {
6 cout << t << endl;
- 0x401362 <main+22>: mov %esi,0x4(%esp)
- 0x401366 <main+26>: movl $0x4740c0,(%esp)
- 0x40136d <main+33>: call 0x448620 <_ZNSolsEi>
- 0x401372 <main+38>: mov %eax,%ebx
7 if ( t == 0 ) {
- 0x4013a5 <main+89>: test %esi,%esi
- 0x4013a7 <main+91>: je 0x4013c8 <main+124>
8 return t;
9 }
10 return f( t - 1 );
- 0x4013a9 <main+93>: dec %esi
- 0x4013aa <main+94>: jmp 0x401362 <main+22>
11 }
You can see that the recursive call has been turned into a jump back to the start of the function. This optimisation is only performed by GCC if the code is compiled with optimisations enabled (-O2 in this case) - perhaps the same is true for MS C++?
Problem
According to answers to that question: Which, if any, C++ compilers do tail-recursion optimization? it seems, that compiler should do tail-recursion optimization. But I've tried proposed options and it seems that compiler can't do this optimization in case of template functions. Could it be fixed somehow?