g++ 中的尾递归问题

Question

我正在搞乱 C++ 中的尾递归函数，并且在使用 g++ 编译器时遇到了一些障碍。

当 numbers[] 大小超过几百个整数时，以下代码会导致堆栈溢出。检查 g++ 生成的汇编代码，发现以下内容表明，twoSum_Helper 正在对其自身执行递归 call 指令。

问题是以下哪一项导致了这种情况？

• 我忽略了以下错误，它阻止了尾递归。
• 我使用 g++ 时犯了一个错误。
• g++ 编译器中检测尾递归函数的缺陷。

我正在 Windows Vista x64 上通过 MinGW 使用 g++ 4.5.0 使用 g++ -O3 -Wall -fno-stack-protector test.c 进行编译。

struct result
{
    int i;
    int j;
    bool found;
};

struct result gen_Result(int i, int j, bool found)
{
    struct result r;
    r.i = i;
    r.j = j;
    r.found = found;
    return r;
}

// Return 2 indexes from numbers that sum up to target.
struct result twoSum_Helper(int numbers[], int size, int target, int i, int j)
{
    if (numbers[i] + numbers[j] == target)
        return gen_Result(i, j, true);
    if (i >= (size - 1))
        return gen_Result(i, j, false);
    if (j >= size)
        return twoSum_Helper(numbers, size, target, i + 1, i + 2);
    else
        return twoSum_Helper(numbers, size, target, i, j + 1);
}

Answer 1

C 或 C++ 中的尾部调用优化极其有限，而且几乎是失败的原因。原因是，通常没有安全的方法从传递指针或对任何局部变量的引用的函数进行尾部调用（作为相关调用的参数，或者实际上是同一函数中的任何其他调用）——当然，这种情况在 C/C++ 领域随处可见，而且几乎是离不开的。

您看到的问题可能是相关的：GCC 可能会通过实际传递分配在调用者堆栈上的隐藏变量的地址来编译返回结构，被调用者将其复制到其中 - 这使其落入上述场景。

Answer 2

尝试使用 -O2 而不是 -O3 进行编译。

如何检查 gcc 是否正在执行尾递归优化？

好吧，无论如何，它不适用于 O2。似乎唯一有效的方法是将结果对象返回到作为参数给出的引用中。

但实际上，删除 Tail 调用并使用循环会更容易。 TCO 在这里是为了优化内联或执行积极展开时发现的尾部调用，但无论如何，您不应该在处理大值时尝试使用递归。

Answer 3

即使在这个简单的函数上，我也无法让 g++ 4.4.0（在 mingw 下）执行尾递归：

static void f (int x)
  {
  if (x == 0) return ;
  printf ("%p\n", &x) ; // or cout in C++, if you prefer
  f (x - 1) ;
  }

我尝试过 -O3、-O2、-fno-stack-protector，C 和 C++ 变体。没有尾递归。

Answer 4

我会看两件事。

1. if 语句中的 return 调用将为当前运行需要解析的函数的堆栈帧中的 else 提供一个分支目标后调用（这意味着任何 TCO 尝试都无法覆盖正在执行的堆栈帧，从而否定 TCO）

2. numbers[] 数组参数是一种可变长度数据结构，它也可以防止 TCO，因为在 TCO 中以某种方式使用相同的堆栈帧。如果调用是自引用的（就像您的），那么它将用新调用的值/引用覆盖堆栈定义的变量（或本地定义的）。如果尾部调用是另一个函数，那么它将用新函数覆盖整个堆栈帧（在 TCO 可以在 A => B => C 中完成的情况下，TCO 可以使这看起来像 A => C执行期间内存中的 C）。我会尝试使用指针。

自从我用 C++ 构建任何东西以来已经有几个月了，所以我没有运行任何测试，但我认为其中一个/两个都阻止了优化。

Answer 5

尝试将您的代码更改为：

// Return 2 indexes from numbers that sum up to target.
struct result twoSum_Helper(int numbers[], int size, int target, int i, int j)
{
    if (numbers[i] + numbers[j] == target)
        return gen_Result(i, j, true);
    if (i >= (size - 1))
        return gen_Result(i, j, false);

    if(j >= size)
        i++; //call by value, changing i here does not matter
    return twoSum_Helper(numbers, size, target, i, i + 1);
}

编辑：根据提问者的评论删除了不必要的参数

// Return 2 indexes from numbers that sum up to target.
struct result twoSum_Helper(int numbers[], int size, int target, int i)
{
    if (numbers[i] + numbers[i+1] == target || i >= (size - 1))
        return gen_Result(i, i+1, true);

    if(i+1 >= size)
        i++; //call by value, changing i here does not matter
    return twoSum_Helper(numbers, size, target, i);
}

Answer 6

C/C++ 中对尾部调用优化 (TCO) 的支持有限。

因此，如果代码依赖 TCO 来避免堆栈溢出，那么最好用循环重写它。否则需要一些自动测试来确保代码得到优化。

通常可以通过以下方式抑制 TCO：

• 将递归函数堆栈上的对象的指针传递给外部函数（在 C++ 的情况下也通过引用传递此类对象）；
• 具有非平凡析构函数的本地对象，即使尾递归有效（析构函数在尾 return 语句之前调用），例如 为什么 g++ 尾部调用不优化，而 gcc 却优化？

这里 TCO 通过按值返回结构而感到困惑。
如果所有递归调用的结果都写入其他函数 twoSum 中分配的相同内存地址，则可以修复它（类似于答案 https://stackoverflow.com/a/30090390/4023446 到 尾递归未发生）

struct result
{
    int i;
    int j;
    bool found;
};

struct result gen_Result(int i, int j, bool found)
{
    struct result r;
    r.i = i;
    r.j = j;
    r.found = found;
    return r;
}

struct result* twoSum_Helper(int numbers[], int size, int target,
    int i, int j, struct result* res_)
{
    if (i >= (size - 1)) {
        *res_ = gen_Result(i, j, false);
        return res_;
    }
    if (numbers[i] + numbers[j] == target) {
        *res_ = gen_Result(i, j, true);
        return res_;
    }
    if (j >= size)
        return twoSum_Helper(numbers, size, target, i + 1, i + 2, res_);
    else
        return twoSum_Helper(numbers, size, target, i, j + 1, res_);
}

// Return 2 indexes from numbers that sum up to target.
struct result twoSum(int numbers[], int size, int target)
{
    struct result r;
    return *twoSum_Helper(numbers, size, target, 0, 1, &r);
}

对于 twoSum_Helper 的所有递归调用，res_ 指针的值都是常量。
从汇编输出（-S 标志）中可以看出，即使有两个递归退出点，twoSum_Helper 尾递归也被优化为循环。

编译选项：g++ -O2 -S（g++ 版本 4.7.2）。

Answer 7

我听到其他人抱怨说，尾递归仅使用 gcc 而不是 g++ 进行优化。
你能尝试使用 gcc 吗？

Answer 8

由于 twoSum_Helper 的代码正在调用自身，因此程序集准确显示发生的情况也就不足为奇了。这就是递归的全部意义:-) 所以这与 g++ 没有任何关系。

每次递归都会创建一个新的堆栈帧，默认情况下堆栈空间是有限的。您可以增加堆栈大小（不知道如何在 Windows 上执行此操作，在 UNIX 上使用 ulimit 命令），但这只能推迟崩溃。

真正的解决方案是摆脱递归。例如，请参阅此问题和这个问题。