对象的尾递归

我有一个递归函数，我想做尾递归。我的实际问题更复杂并且与上下文有关。但我想解决的问题是用这个简单的程序来演示的：对象的尾递归

#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不会优化此。如果我用int替换obj并相应地更改调用，它将按预期变为尾递归。

我的实际问题是：是否有一种简单的方法可以将这个尾递归分开，只需将obj替换为int？我的目标是获得性能优势，因此使用堆分配内存和new最有可能没有帮助。

来源

2016-12-30 IceFire

最简单的方法：获得更好的编译器，无论如何你已经过时了...... –

msvc15不会这样做，要么 – IceFire

你如何期待这个尾递归终止？ –

由于您使用一个临时的，我想你不需要递归调用之后的对象。

一个相当的hackish的解决办法是分配一个对象，一个指针传递给它，并且使递归调用，向其中传递您新构造的对象之前重新分配它。

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，因为它确实是尾递归。

来源

2016-12-30 14:12:57 StoryTeller

好主意，的确如此！但是，我确实需要不要改变这个对象。我的真实故事是，我有部分应该是尾递归的，而其他部分不是......也许，您的解决方案可以用于任何方面，我仍然在寻找一个非参考解决方案 - 如果有任何问题的话，请点击这里 – IceFire

How 'tail_impl'递归结束了吗？ – 0x499602D2

@ 0x499602D2 - 它没有，就像在OP的帖子中一样。他们使用无限递归来测试代码是否被循环代替。如果没有，则会发生堆栈溢出。 – StoryTeller

简短的回答：号

再回应：你可能会找到一种方法来实现这一点，但肯定是不容易的。由于尾调用优化的不是标准所要求的，你永远无法知道，如果你的程序将会使编译器的一些小的改动不能对代码进行优化。

更糟的是，考虑当你需要调试程序时会发生什么。编译器几乎肯定不会使用调试器标志优化高级尾调用，这意味着您的程序只能在发布模式下正常工作。这会使程序难以维护。

替代尾部递归 只需编写一个循环。它总是可以完成的，而且可能会非常复杂，而且更不复杂。它也不使用堆，所以开销会小得多。

来源

2017-01-02 09:36:37

谢谢！你的回答更直截了当，但在大多数情况下，StoryTeller更有帮助，这就是为什么我给他的标志。我希望这是可以理解的 – IceFire

嗯......有用的东西是编写一个循环。我完全忘了在我的回答中提到，所以我现在就添加了它。 :-) –

也是一个很好的想法，谢谢。可悲的是，我再也无法赞成 – IceFire

对象的尾递归

回答

相关问题