c-有没有什么聪明的技巧可以让递归更深入

Question

这是一个打印无限数字的程序。

#define false 0
#define true 1
int test(int idx) {
printf("%dn",idx);
test(idx+1);
return 0;
}
int main() {
test(0);
return 0;
}
// Segmentation fault: 11

此程序在打印262045后以segfault结束。我知道它是由堆栈溢出引起的。

有什么巧妙的技巧可以让递归更深入吗

就像在达到某个数字并清除堆栈时调用另一个递归函数一样？

我试过这样做。

#define false 0
#define true 1
int test2(int idx) {
printf("test2 heren");
printf("%dn",idx);
test2(idx+1);
return 0;
}
int test(int idx) {
if (idx == 262000) {
return test2(idx);
}
printf("%dn",idx);
test(idx+1);
return 0;
}
int main() {
test(0);
return 0;
}

但是堆栈没有被清除。打印262044后仍然存在segfault。

我正在实现正则表达式以匹配文件。我使用递归函数读取并匹配文件，但如果文件太大，就会出现segfault。如果这个问题解决了，我就能解决这个问题。

Answer 1

有什么聪明的技巧可以让递归更深入吗？

递归一开始并不是很聪明，您刚刚发现了其中一个原因。显而易见的"；技巧"；是增加堆栈大小，如果您可以在特定系统上选择这样做的话。

但是，在大多数情况下应该避免递归。在少数情况下，可能有意义，它应该满足两个条件：

• 必须有一种合理且确定的方式来结束递归调用
• 递归调用应该只在函数的末尾，并且每个函数只能有一个这样的调用。所谓的尾调用

尾部调用示例：

int foo (int a)
{
...
return foo(x);
}

这种递归可以由编译器优化为内联循环，即所谓的"递归"；尾部调用优化"；。如果你的编译器不能进行优化，函数就会攻击调用堆栈并杀死它

这意味着，在极少数情况下，递归是有动机的(很少(，您需要反汇编C代码，并确保在机器代码中不会发生递归调用。

Answer 2

正如@Lundin所提到的，这个技巧是使用迭代而不是递归调用的。如果真的想使用递归，你可以使用这样的东西：

int max = 100;
int limited_recursion(int dpt, int param)
{
if (dpt > max)
return param;
if (dpt != 0)
{
printf("%in", param);
return limited_recursion (dpt + 1, param + 1);
}
/* if this is topmost call iterate infititely*/
while (1)
param = limited_recursion (dpt + 1, param);
}
int main(void)
{
limited_recursion(0, 0);
}

然而，还有迭代。递归仅用于演示目的，使代码变得复杂且可读性较差。此代码可以很容易地转换为迭代代码。在这种特殊情况下，它只是一个while循环，将1无限添加到变量中。