When does Stack Overflow occur?

25

A question that has everything to do with the name of this site.

We know that one of the most commonly used examples for demonstrating the execution stack of a program is recursion. A recursive function must have: stop condition and recursion must solve a smaller instance of the same problem.

At runtime the recursive calls will be stacked and then unpinned (executed), from the smallest case to the largest, until the final value is returned.

If there is no stop condition or the recursive call is not for a smaller instance , the program goes into loop Stack Overflow .

Given the following code developed in C:

#include <stdio.h>
#include <conio.h>

int fat(int n);

int main()
{
int n;

printf("Calculo de FATORIAL\n");

printf("Entre com um numero:");
scanf("%d",&n);

printf("Fatorial:%d",fat(n));

getch();
return 0;
}

int fat(int n)
{
 if (n==1)
    return(1);

 return(n * fat(n-1));

}

What would be the execution stack of 4! for example?

If there was no stopping condition, the program would stack until stack overflow occurred. At what point would this occur, ie how big is that stack?

    
asked by Denis Caixeta 01.11.2015 в 18:13
source

1 answer

21

First make sure you understand what is the stack .

It is a portion of memory previously allocated by the application that is being filled as needed by the functions (or scopes). As it enters new scopes it will reserve space (in the part already allocated) for all local variables contained in it (this is called stack frame ). When out of scope, this space is released by moving a pointer indicating where the top of the stack is. Then the space is being used in an accordion effect.

If the code goes into a large sequence of scopes - this is primarily in function calls - the spaces will be reserved and will not be released until you start to get out of these scopes. The stack has a finite space, so an hour may have no more space allocated to reserve, and stack overflow occurs.

This can occur mainly in two situations: very large data allocations in local variables (unnamed) - which is never recommended - that even in a single call of a function can reserve almost every allocated stack, leaving in a state of almost overflow; or, more commonly, make recursive calls without stopping, or stopping too far, as put in the question.

In case of recursion, even with a single simple variable of low memory consumption, it is possible, in thousands of executions, to pop the stack.

In this case the fat function will always have to reserve 4 bytes (typically) for the parameter n (which is a local variable) and probably another 4 bytes for the return of the called function. If you have nothing to stop this, you will accumulate these bytes indefinitely in each call.

The size of the stack varies, and can usually be determined at the time the executable is created. The pattern used may vary too, but it is common for the stack to have 1MB.

When you create threads , a new stack is created. This can be very, and in some cases, little. You can control this.

    
answered by 01.11.2015 / 18:56
source