c++visual-studio-2010tail-recursiontail-call-optimizationtail-call

Visual C++ Tail Call Optimization


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?


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++?