When does Stack Overflow occur?

Question

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

---

We know that one of the most commonly used examples to demonstrate 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.

Recursive calls will be stacked and then popped (executed), from the smallest case to the largest, until the final value is returned.

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

Given the code below 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));

}

How would run stack 4!, for example?

If there was no stopping condition, the program would stack up until battery overflow occurs. At what point this would occur, i.e., how large the stack would be?

Answer 1

First make sure you understand what is the stack.

It is a portion of memory previously allocated by the application that is filled as needed by the functions (or scopes). As the execution goes into new scopes it reserves space (in the already allocated part) for all local variables contained in it (this is called stack frame). When it leaves the scope this space is released by the movement of a pointer (stack Pointer) which indicates where the top of the stack is (its base in memory is indicated by inter-base and is used to calculate the real address because the stack access is always relative to its start and not the whole memory). So space is being used in an accordion effect.

If the code enters a large sequence of scopes - this occurs mainly in function calls - the spaces are being reserved and are not being released, until it starts to leave these scopes. The stack has a finite space, so an hour may not have more space allocated to reserve, and the stack overflow occurs.

This can occur mainly in two situations:

• very large data allocations on local variables (without pointing) - which is never recommended - that even in a single call from a function can reserve almost every allocated stack, leaving in a near-overflow state;
• make recursive calls without stopping, or with very distant stop, as put in question, which is more common.

In the case of recursion, even with a single simple variable of low memory consumption it is possible, in thousands of runs, to burst the stack (some compilers manage to do an optimization eliminating the recursion).

In this case the function fat() always have to reserve 4 bytes (typically) for the parameter n (which is a local variable) and probably another 4 bytes for the callback function. If there is nothing to stop it accumulates these bytes indefinitely in each call.

The stack size varies and, in general, can be determined at the time of creation of the executable. The default used may vary as well, but it is common for the stack to have 1MB in Windows.

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