我在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);
}
return twoSum_Helper(numbers, size, target, i + j_ge_size, j_ge_size ? i + 2 : j + 1)
,其中j_ge_size
是bool j >= size
,它是否有效?(根据自己的喜好进行隐式转换)。 - Tony Delroyextern
,TCO就不再适用——这完全不同。外部链接将有效地推迟调用解析到链接时间,由于GCC默认仅执行非常有限的链接时优化,因此TCO不再适用。但是,函数并不需要是static
才能应用此方法。 - Konrad Rudolph