Does C++11 does optimise away tail recursive calls in lambdas?

Question

My tentative answer is no, as observed by the following test code:

#include <functional>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

void TestFunc (void);
int TestFuncHelper (vector<int>&, int, int);

int main (int argc, char* argv[]) {
    TestFunc ();
    return 0;
} // End main ()

void TestFunc (void) {
    // Recursive lambda
    function<int (vector<int>&, int, int)> r = [&] (vector<int>& v_, int d_, int a_) {
        if (d_ == v_.size ()) return a_;
        else return r (v_, d_ + 1, a_ + v_.at (d_));
    };
    int UpperLimit = 100000; // Change this value to possibly observe different behaviour
    vector<int> v;
    for (auto i = 1; i <= UpperLimit; i++) v.push_back (i);
    // cout << TestFuncHelper (v, 0, 0) << endl; // Uncomment this, and the programme works
    // cout << r (v, 0, 0) << endl; // Uncomment this, and we have this web site
} // End Test ()

int TestFuncHelper (vector<int>& v_, int d_, int a_) {
    if (d_ == v_.size ()) return a_;
        else return TestFuncHelper (v_, d_ + 1, a_ + v_.at (d_));
} // End TestHelper ()

Is there a way to force the compiler to optimise recursive tail calls in lambdas?

Thanks in advance for your help.

EDIT

I just wanted to clarify that I meant to ask if C++11 optimizes recursive tail calls in lambdas. I am using Visual Studio 2012, but I could switch environments if it is absolutely known that GCC does the desired optimization.

Answer 1

You are not actually doing a tail-call in the "lambda" code, atleast not directly. std::function is a polymorphic function wrapper, meaning it can store any kind of callable entity. A lambda in C++ has a unique, unnamed class type and is not a std::function object, they can just be stored in them.

Since std::function uses type-erasure, it has to jump through several hoops to call the thing that was originally passed to it. These hoops are commenly done with either virtual functions or function-pointers to function template specializations and void*.

The sole nature of indirection makes it very hard for optimizers to see through them. In the same vein, it's very hard for a compiler to see through std::function and decide whether you have a tail-recursive call.

Another problem is that r may be changed from within r or concurrently, since it's a simple variable, and suddenly you don't have a recursive call anymore! With function identifiers, that's just not possible, they can't change meanings mid-way.

I just wanted to clarify that I meant to ask if C++11 optimizes recursive tail calls in lambdas.

The C++11 standard describes how a working program on an abstract machine behaves, not how the compiler optimizes stuff. In fact, the compiler is only allowed to optimize things if it doesn't change the observable behaviour of the program (with copy-elision/(N)RVO being the exception).