c++ - g++中的尾递归问题

Question

我正在研究 C++ 中的尾递归函数，并且在使用 g++ 编译器时遇到了一些问题。

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

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

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

我正在通过带有 g++ 4.5.0 的 MinGW 在 Windows Vista x64 上使用 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 可能通过实际传递分配在调用者堆栈上的隐藏变量的地址来编译返回一个结构，被调用者将其复制到其中——这使得它属于上述情况。