Может ли это быть оптимизировано с помощью хвостового вызова? Если так, то в чем особая причина того, что этого не произошло?

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

8

c++tail-recursion

Решение

Другие решения

Просто для справки, я настроил рекурсивную версию, чтобы получить хвостовую рекурсию, к этому:

#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();
}

2

Вы не должны полагаться на хвостовой вызов для этого. Я думаю, что вряд ли оптимизатор заметит, что и то и другое рекурсивные вызовы могут быть оптимизированы с помощью хвоста.

Вот нерекурсивная версия.

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

1

Источник

Accepted Answer

Деструктор для vector<unsigned> параметр должен быть вызван после возврата.

12