Хвост-рекурсия с объектами

Question

У меня есть рекурсивная функция, которую я хотел бы сделать хвостом-рекурсивным. Моя фактическая проблема более сложна и зависит от контекста. Но проблема, которую я хотел бы решить, продемонстрирована с помощью этой простой программы:

#include <iostream> 

struct obj 
{ 
    int n; 

    operator int&() { return n; } 
}; 

int tail(obj n) 
{ 
    return tail(obj{ n + 1 > 1000 ? n - 1000 : n + 1 }); 
} 

int main() 
{ 
    tail(obj{ 1 }); 
} 

Кажется естественным, что это хвостовое рекурсивно. Это не так, потому что деструктор obj n должен вызываться каждый раз. По крайней мере, MSVC13 (изменить :) и MSVC15 не оптимизируйте это. Если я заменил obj на int и соответствующим образом изменил бы вызовы, он станет хвостовым рекурсивным, как ожидалось.

Мой фактический вопрос: есть ли простой способ сделать этот хвостовой рекурсивный, кроме замены obj на int? Я стремлюсь к преимуществам производительности, поэтому играть с выделенной памятью и new, скорее всего, не поможет.

Answer 1

Поскольку вы используете временное, я предполагаю, что вам не нужен объект после рекурсивного вызова.

Одним из довольно хакерских решений является выделение объекта, передача указателя на него и перераспределение его перед выполнением рекурсивного вызова, которому вы передаете вновь созданный объект.

struct obj 
{ 
    int n; 

    operator int&() { return n; } 
}; 

int tail_impl(obj*& n) 
{ 
    int n1 = *n + 1 > 1000 ? *n - 1000 : *n + 1; 
    delete n; 
    n = new obj{n1}; 
    return tail_impl(n); 
} 

int tail(obj n) 
{ 
    obj *n1 = new obj{n}; 
    auto ret = tail_impl(n1); 
    delete n1; 
    return ret; 
} 

int main() 
{ 
    tail(obj{ 1 }); 
} 

Я, очевидно, опустил некоторые важные сведения о безопасности безопасности. Однако GCC is able to turn tail_impl into a loop, так как это действительно рекурсия хвоста.

Answer 2

Короткий ответ: No.

Longer Ответ: Вы могли бы найти способ для достижения этой цели, но, конечно, не легко. Поскольку оптимизация вызова вызова не требуется стандартом, вы никогда не сможете точно знать, будут ли некоторые незначительные изменения в вашей программе заставлять компилятор не оптимизировать код.

Хуже, подумайте, что произойдет, когда вам нужно отладить вашу программу. Компилятор почти наверняка не оптимизирует передовые хвостовые вызовы с флагами отладчика, а это значит, что ваша программа будет работать только в режиме деблокирования. Это усложнит работу программы.

Альтернатива хвостовой рекурсии Просто напишите цикл. Это всегда можно сделать, и это, вероятно, будет намного, намного менее запутанным. Он также не использует кучу, поэтому накладные расходы будут намного меньше.