Как указано @celtschk's answer, нетривиальные деструкторы не позволяют компилятору обрабатывать вызовы как по-настоящему хвостовые рекурсивные. Даже если ваша функция сводятся к следующему:
template<typename T, T (*funct)(int) >
multiset<T> Foo(const multiset<T>& bar, int iterations) {
if (iterations == 0) return bar;
return Foo<T,funct>(bar, iterations - 1);
}
Это еще не хвостовая рекурсии, из-за неявные вызовы к нетривиальным конструкторам и деструкторам в результате вызова рекурсивной функции.
Однако следует отметить, что данная функция действительно становится хвостовой рекурсией с относительно небольшим изменением:
template<typename T, T (*funct)(int) >
const multiset<T>& Foo(const multiset<T>& bar, int iterations) {
if (iterations == 0) return bar;
return Foo<T,funct>(bar, iterations - 1);
}
Voila! Теперь функция скомпилируется в цикл. Как мы можем добиться этого с помощью вашего исходного кода?
К сожалению, это немного сложно, потому что ваш код иногда возвращает копию, а иногда и исходный аргумент. Мы должны правильно разобраться с обоими случаями. Решение, представленное ниже, представляет собой вариацию идеи David, упомянутой в его комментариях к его ответу.
Предполагая, что вы хотите оставить свою оригинальную подпись Foo
той же (и, поскольку она иногда возвращает копию, нет оснований полагать, что вы не захотите оставить подпись тем же), мы создаем вторичную версию Foo
называется Foo2
, который возвращает ссылку на объект результата, который является либо исходным параметром bar
, либо одним локальным в вашем Foo
. Кроме того, Foo
создает место объекты держатель для копирования, вторичная копия (для переключения), и один для хранения результата funct()
вызова:
template<typename T, T (*funct)(int) >
multiset<T> Foo(const multiset<T>& bar, int iterations) {
multiset<T> copy_bar;
multiset<T> copy_alt;
T baz;
return Foo2<T, funct>(bar, iterations, copy_bar, copy_alt, baz);
}
С Foo2
всегда будет в конечном итоге возвращает ссылку, это снимает любые вопросы с результатом рекурсивной функции, вызывающим неявное построение и разрушение.
На каждой итерации, если копия будет использоваться в качестве следующего bar
, мы передаем копию, но переключим порядок копирования и альтернативные заполнители для рекурсивного вызова, чтобы альтернативный вариант фактически использовался для хранения копию на следующей итерации. Если следующая итерация повторяется bar
как есть, порядок аргументов не изменяется, счетчик iterations
просто уменьшается.
template<typename T, T (*funct)(int) >
const multiset<T>& Foo2(
const multiset<T>& bar, int iterations,
multiset<T>& copy_bar, multiset<T>& copy_alt, T& baz) {
if (iterations == 0) return bar;
copy_bar = bar;
baz = funct(copy_bar.size());
if (baz.attr > 0) {
return Foo2<T, funct>(copy_bar, 100, copy_alt, copy_bar, baz);
} else {
return Foo2<T, funct>(bar, --iterations, copy_bar, copy_alt, baz);
}
}
Обратите внимание, что только первоначальный вызов Foo
платит штраф строительства и уничтожения локальных объектов, и Foo2
теперь полностью хвостовой рекурсией.
Каков вклад функции? Без этой функции трудно сказать, что не так – Matt
@Matt Я думаю, что 'funct' в данном случае не имеет значения. Когда я запускаю 'gdb', в стеке есть только вызовы Foo, потому что вызывался' funct', а затем он возвращался. – Jcao02
Что происходит, если вы назначаете переменные в свой оператор 'if/else' и имеете только один вызов' Foo' в конце? –