对象的尾递归

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 (edit:) 和 MSVC15 没有对此进行优化。如果我用 int 替换 obj 并相应地更改调用，它会按预期变为尾递归。

我的实际问题是：除了将 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

简答：没有。

更长的答案：您可能会找到一种方法来实现这一点，但肯定不容易。由于标准不要求尾调用优化，因此您永远无法确定对程序的一些小改动是否会导致编译器无法优化代码。

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

替代尾递归 只写一个循环。它总是可以完成的，而且很可能不会那么复杂。它也不使用堆，所以开销会小很多。

对象的尾递归

Tail-recursion with objects

c++

recursion

tail-recursion