7

如果一个函数在定义变量的同时调用自己会导致堆栈溢出吗？gcc 中是否有任何选项可以重用相同的堆栈。

void funcnew(void)
{
   int a=10;
   int b=20;
   funcnew();
   return ;
 }

函数可以重用它之前使用的堆栈帧吗？gcc 中有什么选项可以在尾递归中重用相同的帧？

4

6 回答 6

5

是的。看

-foptimize-sibling-calls

优化兄弟和尾递归调用。

在 -O2、-O3、-Os 级别启用。

您的函数编译为：

funcstack:
.LFB0:
    .cfi_startproc
    xorl    %eax, %eax
    jmp func
    .cfi_endproc

（注意跳转到func）

当函数通过调用结束时重用堆栈帧 - 这包括在其全部通用性中操纵堆栈以将参数放在正确的位置并通过跳转到函数的开头替换函数调用 - 是众所周知的优化称为 [i]tail call removal[/i]。某些语言（例如方案）要求递归调用（递归调用是在这些语言中表达循环的自然方式）。如上所述，gcc 为 C 实现了优化，但我不确定哪个其他编译器有它，我不会依赖它来实现可移植代码。请注意，我不知道它有哪些限制——例如，如果参数类型不同，我不确定 gcc 是否会操纵堆栈。

于 2010-02-12T09:37:09.747 回答
3

即使没有定义参数，你也会得到一个 stackoverflow。由于返回地址也被压入堆栈。

编译器可能会将您的循环优化为尾递归（这使得堆栈根本不会增长）（我最近了解到这一点）。链接到关于 SO 的尾递归问题

于 2010-02-12T09:33:08.273 回答
0

不，每个递归都是一个新的堆栈帧。如果递归是无限深的，那么所需的堆栈也是无限的，所以会出现堆栈溢出。

于 2010-02-12T09:24:10.680 回答
0

是的，在某些情况下，编译器可能能够执行称为尾调用优化的操作。你应该检查你的编译器手册。（AProgrammer 似乎在他的回答中引用了 GCC 手册。）

在实现例如频繁出现此类代码的函数式语言时，这是一项必不可少的优化。

于 2010-02-12T09:37:44.690 回答
0

您不能完全取消堆栈帧，因为返回地址需要它。除非您使用尾递归，并且您的编译器已将其优化为循环。但老实说，您可以通过将框架中的所有变量设为静态来消除框架中的所有变量。但是，这几乎可以肯定不是您想要做的，并且您不应该在不确切知道自己在做什么的情况下这样做，因为您不得不问这个问题，但您不知道。

于 2010-02-12T09:38:25.140 回答
0

正如其他人所指出的，只有在 (1) 您的编译器支持尾调用优化，以及 (2) 如果您的函数有资格进行此类优化时，才有可能。优化是重用现有堆栈并执行 JMP（即汇编中的 GOTO）而不是 CALL。

事实上，您的示例函数确实有资格进行这种优化。原因是你的函数在返回之前做的最后一件事就是调用它自己；在最后一次调用funcnew(). 但是，只有某些编译器会执行这样的优化。例如，GCC 会这样做。有关更多信息，请参阅哪些 C++ 编译器（如果有）进行尾递归优化？

这方面的经典材料是阶乘函数。让我们创建一个不符合尾调用优化 (TCO) 条件的递归阶乘函数。

int fact(int n)
{
  if ( n == 1 ) return 1;
  return n*fact(n-1);
}

它做的最后一件事是n与 的结果相乘fact(n-1)。通过以某种方式消除最后一个操作，我们将能够重用堆栈。让我们引入一个累加器变量，它将为我们计算答案：

int fact_helper(int n, int acc)
{
  if ( n == 1 ) return acc;
  return fact_helper(n-1, n*acc);
}

int fact_acc(int n)
{
  return fact_helper(n, 1);
}

该函数fact_helper完成工作，而fact_acc只是初始化累加器变量的便捷函数。

请注意最后一件事fact_helper是如何调用自身。通过重用变量的现有堆栈，可以将此 CALL 转换为 JMP。

使用 GCC，您可以通过查看生成的程序集来验证它是否已针对跳转进行了优化，例如gcc -c -O3 -Wa,-a,-ad fact.c：

  ...
  37                    L12:
  38 0040 0FAFC2                imull   %edx, %eax
  39 0043 83EA01                subl    $1, %edx
  40 0046 83FA01                cmpl    $1, %edx
  41 0049 75F5                  jne     L12
  ...

一些编程语言，例如Scheme，实际上会保证正确的实现会执行这样的优化。他们甚至会为非递归尾调用做到这一点。

于 2011-05-13T13:53:32.063 回答