Odpowiedź.

Przepełnienie stosu (stack overflow) to sytuacja, w której program zużywa więcej pamięci stosu, niż przydzielił system. Historycznie stos był używany do przechowywania zmiennych lokalnych, adresów powrotu i danych tymczasowych podczas wywołań funkcji. Wczesne implementacje C miały stos o dość małych rozmiarach i nie były chronione przed przepełnieniem.

Problem występuje, gdy funkcja lub łańcuch wywołań funkcji wykorzystuje zbyt wiele zmiennych lokalnych lub wywołuje funkcje rekurencyjne bez warunku zakończenia, co prowadzi do zapisywania danych poza przydzieloną pamięcią stosu, powodując błędy, awarie i podatności.

Rozwiązanie — projektowanie funkcji o skromnym zużyciu pamięci, unikanie głębokich lub nieskończonych rekurencji, nie umieszczanie dużych obiektów na stosie. System operacyjny może zapobiegać przepełnieniu za pomocą ochrony segmentów pamięci (guard pages), jednak programista ma obowiązek pisać kod, który nie powoduje przepełnienia.

Przykład kodu wywołującego stack overflow z powodu nieskończonej rekurencji:

void foo() {
    int arr[1000]; // Duża lokalna tablica tylko przyspiesza problem
    foo(); // Rekursywne wywołanie bez zakończenia
}

int main() {
    foo();
    return 0;
}

Kluczowe cechy:

Stos ma ograniczony rozmiar; jego przekroczenie powoduje błąd lub awarię.
Głęboka lub niekontrolowana rekurencja to główny powód przepełnienia.
Kontrola umiejscowienia dużych danych na stosie to odpowiedzialność programisty.

Pytania z pułapką.

Co się stanie, jeśli zadeklarujesz bardzo dużą lokalną tablicę wewnątrz funkcji (na przykład int arr[1000000])?

Odpowiedź: Duża lokalna tablica może natychmiast wykorzystać całą pamięć stosu. W zależności od systemu operacyjnego i kompilatora, może to doprowadzić do awarii podczas uruchamiania funkcji lub nawet do zablokowania programu.

Przykład kodu:

void func() {
    int arr[1000000]; // Bardzo dużo pamięci
    arr[0] = 1;
}

Czy rekurencja zawsze prowadzi do przepełnienia stosu?

Odpowiedź: Nie, rekurencja jest użyteczna, jeśli jest ograniczona pod względem głębokości. Przepełnienie występuje tylko wtedy, gdy głębokość rekurencji jest duża lub nie jest ograniczona.

Czy można umieszczać duże statyczne tablice wewnątrz funkcji w celu oszczędności pamięci?

Odpowiedź: Nie, duże statyczne tablice wewnątrz funkcji nadal zajmują pamięć, ale w segmencie danych statycznych, a nie na stosie. Nie zawsze jest to ekonomiczne, szczególnie jeśli potrzebna jest tymczasowa pamięć lokalna.

Przykład kodu:

void func() {
    static int arr[1000000]; // Nie na stosie, ale obszar statyczny zajęty na zawsze
}

Typowe błędy i antywzorce

Umieszczanie dużych tablic/struktur na stosie.
Używanie niekontrolowanej rekurencji.
Ignorowanie kontroli głębokości rekurencji w funkcjach.

Przykład z życia

Negatywny przypadek

Programista zaimplementował algorytm sortowania przez szybkie sortowanie za pomocą rekurencji dla dużej tablicy, nie ograniczając głębokości wywołań i nie stosując warunków zakończenia. Kod prowadził do stack overflow podczas przetwarzania rzeczywistych danych.

Zalety:

Piękna i zwięzła rekurencyjna implementacja.

Wady:

Rzeczywista niedostępność algorytmu dla dużych danych, częste awarie.
Awaria programu w boju.

Pozytywny przypadek

Inny programista wykorzystał iteracyjną implementację z własnym małym stosem na stercie, kontrolował głębokość rekurencji i przydzielał dużą pamięć tymczasową za pomocą malloc.