g ++中的尾递归问题
我正在用C ++中的尾递归函数搞乱,而且我碰到了g ++编译器的一些问题。
当numbers[]
超过几百个整数时,以下代码会导致堆栈溢出。 检查由g ++生成的汇编代码如下所示,显示twoSum_Helper正在对其自身执行递归call
指令。
问题是以下哪一项导致了这个问题?
我使用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);
}
C或C ++中的尾部调用优化是非常有限的,几乎是失败的原因。 原因在于通常没有安全的方法来从传递指针或引用到任何局部变量的函数(作为所讨论的调用的参数,或实际上在同一函数中的任何其他调用)进行尾部调用 - 这当然是在C / C ++领域发生的,几乎不可能没有。
您看到的问题可能与以下相关:GCC可能编译通过实际传递在调用者的堆栈中分配的隐藏变量的地址来返回一个结构,被调用者将其复制到其中 - 这使得它陷入上述场景。
尝试使用-O2代替-O3。
如何检查gcc是否执行尾递归优化?
好吧,它无论如何都不适用于O2。 似乎工作的唯一东西是将result
对象返回给参数给出的参数。
但实际上,仅仅删除尾部呼叫并使用循环代替它会容易得多。 TCO在此优化在内联或进行积极展开时发现的尾部调用,但无论如何您都不应尝试使用递归处理较大的值。
我无法得到g ++ 4.4.0(在mingw下)执行尾递归,即使在这个简单的函数上:
static void f (int x)
{
if (x == 0) return ;
printf ("%pn", &x) ; // or cout in C++, if you prefer
f (x - 1) ;
}
我已经尝试了-O3
, -O2
, -fno-stack-protector
,C和C ++变体。 没有尾递归。