Could this optimize the tail call? If so, what special reason for this will not happen?

Question

I tested the build at many optimization levels with both gcc 4.8.1 and clang 3.4.190255, without tail call optimization for this type of code.

Any special reason collatz_aux not receiving tail call optimization?

 #include <vector> #include <cassert> using namespace std; vector<unsigned> concat(vector<unsigned> v, unsigned n) { v.push_back(n); return v; } vector<unsigned> collatz_aux(unsigned n, vector<unsigned> result) { return n == 1 ? result : n % 2 == 0 ? collatz_aux(n / 2, concat(move(result), n)) : collatz_aux(3 * n + 1, concat(move(result), n)); } vector<unsigned> collatz_vec(unsigned n) { assert(n != 0); return collatz_aux(n, {}); } int main() { return collatz_vec(10).size(); } 

Answer 1

The destructor for the vector<unsigned> parameter must be called after the return.

Answer 2

Just for reference, I modified the recursive version to get tail recursion to:

 #include <vector> #include <cassert> using namespace std; template<class container> container &&collatz_aux(unsigned n, container &&result) { static auto concat = [](container &&c, unsigned n) -> container &&{ c.push_back(n); return forward<container>(c); }; return n == 1 ? forward<container>(result) : n % 2 == 0 ? collatz_aux(n / 2, concat(forward<container>(result), n)) : collatz_aux(3 * n + 1, concat(forward<container>(result), n)); } vector<unsigned> collatz_vec(unsigned n) { assert(n != 0); return collatz_aux(n, vector<unsigned>{}); } int main() { return collatz_vec(10).size(); } 

Answer 3

You should not rely on tail-call for this. I think it is unlikely that the optimizer will find that recursive calls can be tail-optimized either.

Here's a non-recursive version.

 vector<unsigned> collatz_aux(unsigned n, vector<unsigned> result) { while(true){ if(n == 1) return result; result = concat(move(result), n); if(n % 2 == 0) { n=n / 2; }else{ n= 3 * n + 1; } } }