g ++中尾部递归的问题

Question

我正在用C++搞乱尾递归函数,而且我在使用g ++编译器时遇到了一些麻烦.

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

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

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

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

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

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

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

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