c++ - 这可以进行尾调用优化吗？如果是这样，它没有发生的特殊原因是什么？

Question

我已经使用 gcc 4.8.1 和 clang 3.4.190255 检查了许多优化级别的程序集输出，这种代码没有尾调用优化。

collatz_aux为什么没有得到尾调用优化的任何特殊原因？

#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

参数的析构vector<unsigned>函数需要在返回后调用。

Answer 2

仅供参考，我调整了递归版本，以获得尾递归：

#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

您不应该为此依赖尾声。我认为优化器不太可能发现两个递归调用都可以进行尾部优化。

这是一个非递归版本。

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;
    }
  }
}