常见的编译器优化是将尾递归函数转化为循环，加快执行时间，减少内存(堆栈)消耗:
int go_to_zero( int n )
{
if( n == 0 )
return 0;
else
return go_to_zero( n - 1 );
}
我的问题很简单:在模板元编程中使用尾递归算法是否有任何性能优势(即减少编译时间)？
这里是一个例子:
template<typename... Ts>
struct list {};
template<typename LIST>
struct reverse;
template<typename HEAD , typename... TAIL>
struct reverse<list<HEAD,TAIL...>>
{
using result = concat<typename reverse<list<TAIL...>>::result,list<HEAD>>;
};
template<>
struct reverse<list<>>
{
using result = list<>;
};
对比:
template<typename INPUT , typename OUTPUT>
struct reverse_impl;
template<typename HEAD , typename... TAIL , tyename... Ts>
struct reverse_impl<list<HEAD,TAIL...>,list<Ts...>>
{
using result = typename reverse_impl<list<TAIL...>,list<Ts...,HEAD>>::result;
};
template<typename... Ts>
struct reverse_impl<list<>,list<Ts...>>
{
using result = list<Ts...>;
};
template<typename LIST>
using reverse = typename reverse_impl<LIST,list<>>::result;
最佳答案
在 C++ Template Metaprogramming附录 C “编译时间性能” Abraham 和 Gurtovoy 弄乱了模板实例化的内存如何影响编译时间。这本书写于 2005 年，我认为记忆化在今天得到了更好的实现(我没有测量)。所以要回答的问题是哪种实现可以从内存中获益更多。我稍微编辑了代码Version 1和 Version 2 .现在它会在 reverse_impl 时发出错误。是实例化的，所以我们可以简单地计算错误。我反转了 2 个列表 list<int, short, char>和 list<short, char> .版本 1 发出 4 个错误，版本 2 发出 7 个错误。在这种特殊情况下，版本 1 受益于这两个列表的内存(list2 是 list1 的尾部)，而版本 2 则没有。所以我希望第 1 版更快。
因此，最好根据已知可以从记忆化中受益的其他算法来实现算法，我认为它们中的大多数都使用头递归。
关于c++ - 模板元编程的尾递归性能，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22449902/