7

if a function calls itself while defining variables at the same time would it result in stack overflow? Is there any option in gcc to reuse the same stack.

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

can a function reuse the stack-frame which it used earlier? What is the option in gcc to reuse the same frame in tail recursion??

Ether
  • 53,118
  • 13
  • 86
  • 159
lazy_hack
  • 301
  • 1
  • 2
  • 6

6 Answers6

5

Yes. See

-foptimize-sibling-calls

Optimize sibling and tail recursive calls.

Enabled at levels -O2, -O3, -Os.

Your function is compiled to:

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

(note the jump to func)

Reusing the stack frame when a function end by a call -- this include in its full generality manipulating the stack to put the parameters at the correct place and replacing the function call by a jump to the start of the function -- is a well known optimisation called [i]tail call removal[/i]. It is mandated by some languages (scheme for instance) for recursive calls (a recursive call is the natural way to express a loop in these languages). As given above, gcc has the optimisation implemented for C, but I'm not sure which other compiler has it, I would not depend on it for portable code. And note that I don't know which restriction there are on it -- I'm not sure for instance that gcc will manipulate the stack if the parameters types are different.

AProgrammer
  • 51,233
  • 8
  • 91
  • 143
3

Even without defining the parameters you'd get a stackoverflow. Since the return address also is pushed onto the stack.

It is (I've learned this recently) possible that the compiler optimizes your loop into a tail recursion (which makes the stack not grow at all). Link to tail recursion question on SO

Community
  • 1
  • 1
Toad
  • 15,593
  • 16
  • 82
  • 128
  • Tail recursion does not apply here; to do tail-call-optzn, the call has to be the last thing the function does. To avoid an infinite loop, there must be some terminating case where the function returns w/o another recursive call. Neither of things cases apply to the code in the question. – Tim Schaeffer Feb 12 '10 at 16:56
  • 2
    @tim: The recursive call IS the last thing the function does. The return is a statement which has no effect and can be left out. I agree that the function doesn't terminate and it would cause an infinite loop. However it would not cause a stackoverflow if it was optimized for tail recursion by the compiler. – Toad Feb 12 '10 at 19:37
0

No, each recursion is a new stack frame. If the recursion is infinitely deep, then the stack needed is also infinite, so you get a stack overflow.

John Knoeller
  • 33,512
  • 4
  • 61
  • 92
0

Yes, in some cases the compiler may be able to perform something called tail call optimization. You should check with your compiler manual. (AProgrammer seems to have quoted the GCC manual in his answer.)

This is an essential optimization when implementing for example functional languages, where such code occurs frequently.

Hans W
  • 3,851
  • 1
  • 22
  • 21
0

You can;t do away with the stack frame altogether, as it is needed for the return address. unless you are using tail-recursion, and your compiler has optimised it to a loop. But to be completely technically honest, you can do away with all the variables in the the frame by making them static. However, this is almost certainly not what you want to do, and you should not do it without knowing exactly what you are doing, which as you had to ask this question, you don't.

0

As others have noted, it is only possible if (1) your compiler supports tail call optimization, and (2) if your function is eligible for such an optimization. The optimization is to reuse the existing stack and perform a JMP (i.e., a GOTO in assembly) instead of a CALL.

In fact, your example function is indeed eligible for such an optimization. The reason is that the last thing your function does before returning is call itself; it doesn't have to do anything after the last call to funcnew(). However, only certain compilers will perform such an optimization. GCC, for instance, will do it. For more info, see Which, if any, C++ compilers do tail-recursion optimization?

The classic material on this is the factorial function. Let's make a recursive factorial function that is not eligible for tail call optimization (TCO).

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

The last thing it does is to multiply n with the result from fact(n-1). By somehow eliminating this last operation, we would be able to reuse the stack. Let's introduce an accumulator variable that will compute the answer for us:

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);
}

The function fact_helper does the work, while fact_acc is just a convenience function to initialize the accumulator variable.

Note how the last thing fact_helper does is to call itself. This CALL can be converted to a JMP by reusing the existing stack for the variables.

With GCC, you can verify that it is optimized to a jump by looking at the generated assembly, for instance 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
  ...

Some programming languages, such as Scheme, will actually guarantee that proper implementations will perform such optimizations. They will even do it for non-recursive tail calls.

Community
  • 1
  • 1
csl
  • 10,937
  • 5
  • 57
  • 89