C Academy · Lekcja

Unikanie przepełnienia stosu

Ograniczy Pan/Pani głębokość rekurencji.

Unikanie przepełnienia stosu to bezpłatna lekcja C Academy na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej C Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs C Academy zawiera 4 lekcji w sumie.

Czym jest przepełnienie stosu?

Stos wywołań ma ograniczony rozmiar. Każde wywołanie funkcji wykorzystuje jego część na parametry i zmienne lokalne.

Jeśli rekurencja stanie się zbyt głęboka, stos się zapełni, a program zakończy działanie z powodu przepełnienia stosu.

Brak przypadku bazowego

Najczęstszą przyczyną jest przypadek bazowy, który nigdy nie zostaje osiągnięty. Powoduje to nieskończoną rekurencję i przepełnienie stosu.

Proszę nie uruchamiać tego rodzaju funkcji; należy przeanalizować, dlaczego zawodzi.

int broken(int n) {
    /* no base case: never stops */
    return broken(n + 1);
}

Argument się nie zmniejsza

Nawet jeśli istnieje przypadek bazowy, argument musi się do niego zbliżać. Tutaj n rośnie, więc nigdy nie osiąga wartości 0.

Proszę zawsze sprawdzać, czy każde wywołanie przybliża się do warunku zakończenia.

int oops(int n) {
    if (n == 0) return 0;
    return oops(n + 1); /* wrong direction */
}

Poprawna wersja

Zmiana kierunku sprawia, że funkcja się kończy. Teraz n zmniejsza się w kierunku przypadku bazowego 0.

#include <stdio.h>

int good(int n) {
    if (n == 0) return 0;
    return n + good(n - 1);
}

int main(void) {
    printf("%d\n", good(10));
    return 0;
}

Ograniczenia głębokości są rzeczywiste

Nawet poprawna rekurencja może doprowadzić do przepełnienia stosu, jeśli jest bardzo głęboka. Wywołanie funkcji na milionach poziomów może przekroczyć rozmiar stosu, który często wynosi zaledwie kilka megabajtów.

W przypadku bardzo dużej głębokości należy wybrać iterację.

Zamiana głębokiej rekurencji na pętlę

Jeśli głębokość rekurencji rośnie wraz z rozmiarem danych wejściowych, należy użyć pętli. Pozwala to uniknąć odkładania tysięcy ramek.

Poniższa pętla bezpiecznie sumuje liczby od 1 do dużej wartości n, korzystając ze stałej ilości pamięci.

#include <stdio.h>

int main(void) {
    long total = 0;
    for (int i = 1; i <= 1000000; i++)
        total += i;
    printf("%ld\n", total);
    return 0;
}

Zmniejszanie głębokości przez dziel i zwyciężaj

Dzielenie pracy na połowy pozwala utrzymać niewielką głębokość. Sumowanie zakresu przez dzielenie go na połowy sprawia, że głębokość rośnie jak logarytm rozmiaru, a nie liniowo.

long range_sum(int lo, int hi) {
    if (lo == hi) return lo;
    int mid = (lo + hi) / 2;
    return range_sum(lo, mid) + range_sum(mid + 1, hi);
}

Uwaga na duże tablice lokalne

Duże zmienne lokalne sprawiają, że każda ramka zajmuje dużo miejsca, przez co stos zapełnia się szybciej.

Proszę unikać deklarowania dużych tablic wewnątrz funkcji rekurencyjnej; zamiast tego należy przekazywać wskaźniki lub korzystać ze sterty.

void heavy(int n) {
    int buffer[10000]; /* big frame each call */
    if (n == 0) return;
    heavy(n - 1);
}

Korzystanie z akumulatora

Przekazywanie bieżącej sumy jako akumulatora pozwala zmniejszyć rozmiar każdej ramki i nadaje rekurencji postać ogonową.

Niektóre kompilatory mogą wtedy ponownie wykorzystać pojedynczą ramkę.

#include <stdio.h>

long sum_acc(int n, long acc) {
    if (n == 0) return acc;
    return sum_acc(n - 1, acc + n);
}

int main(void) {
    printf("%ld\n", sum_acc(100, 0));
    return 0;
}

Lista kontrolna bezpieczeństwa

Przed użyciem funkcji rekurencyjnej proszę sprawdzić:

1. Czy istnieje przypadek bazowy?
2. Czy każde wywołanie przybliża się do tego przypadku?
3. Czy dla dużych danych wejściowych głębokość może stać się bardzo duża?

Jeśli głębokość może gwałtownie wzrosnąć, należy zamiast tego użyć pętli.

Testowanie na małych danych wejściowych

Rekurencję należy zawsze najpierw testować na bardzo małych danych wejściowych, których wynik można sprawdzić ręcznie.

Jeśli małe przypadki działają poprawnie, a głębokość pozostaje ograniczona, można z większą pewnością zwiększyć rozmiar danych.

Szybkie sprawdzenie

Proszę wskazać najbezpieczniejsze rozwiązanie.

Podsumowanie

Przepełnienie stosu występuje, gdy rekurencja staje się zbyt głęboka lub nigdy się nie kończy. Należy zawsze zapewnić osiągalny przypadek bazowy, zmniejszać argument przy każdym wywołaniu, ograniczać rozmiar ramek i przechodzić na iterację, gdy głębokość może rosnąć wraz z rozmiarem danych wejściowych.

Często zadawane pytania

Czy lekcja „Unikanie przepełnienia stosu” jest bezpłatna?

Tak — pełny tekst „Unikanie przepełnienia stosu” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu C Academy, przejdź na CoddyKit PRO. Kurs C Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Unikanie przepełnienia stosu”?

Ograniczy Pan/Pani głębokość rekurencji. Ćwiczysz C Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć C Academy?

Nie wymagamy żadnego doświadczenia. C Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.

Ile czasu zajmuje lekcja „Unikanie przepełnienia stosu”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji C Academy?

Tak. Każda lekcja C Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

← Powrót do C Academy