Undvik stack overflow
Begränsa rekursionen.
Undvik stack overflow är en gratis lektion i C Academy på CoddyKit. Detta är lektion 4 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för C Academy, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i C Academy innehåller totalt 4 lektioner.
Vad är stack overflow?
Call stack har en begränsad storlek. Varje funktionsanrop använder en del av den för parametrar och lokala variabler.
Om rekursionen blir för djup fylls stacken och programmet kraschar med en stack overflow.
Basfall saknas
Den vanligaste orsaken är ett basfall som aldrig nås. Då fortsätter anropen för evigt och stacken svämmar över.
Kör inte den här typen av funktion; undersök varför den misslyckas.
int broken(int n) {
/* no base case: never stops */
return broken(n + 1);
}Argumentet minskar inte
Även om det finns ett basfall måste argumentet närma sig det. Här ökar n, så det når aldrig 0.
Kontrollera alltid att varje anrop kommer närmare stoppvillkoret.
int oops(int n) {
if (n == 0) return 0;
return oops(n + 1); /* wrong direction */
}En korrekt version
Om riktningen rättas till avslutas funktionen. Nu minskar n mot basfallet 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;
}Djupgränser är verkliga
Även korrekt rekursion kan orsaka stack overflow om den blir mycket djup. Om en funktion anropas miljontals nivåer djupt kan stacken överskridas; den är ofta bara några megabyte stor.
Vid mycket stora djup bör du föredra iteration.
Omvandla djup rekursion till en loop
Om rekursionsdjupet växer med indatans storlek bör du byta till en loop. Då undviker du att stapla tusentals stackramar.
Loopen nedan summerar säkert 1 till ett stort n med konstant minnesanvändning.
#include <stdio.h>
int main(void) {
long total = 0;
for (int i = 1; i <= 1000000; i++)
total += i;
printf("%ld\n", total);
return 0;
}Minska djupet med divide-and-conquer
Genom att dela arbetet på mitten hålls djupet litet. Om ett intervall summeras genom halvering växer djupet som logaritmen av storleken i stället för linjärt.
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);
}Se upp med stora lokala arrayer
Stora lokala variabler gör varje stackram tung, så stacken fylls snabbare.
Undvik att deklarera stora arrayer i en rekursiv funktion; skicka pekare eller använd heapen i stället.
void heavy(int n) {
int buffer[10000]; /* big frame each call */
if (n == 0) return;
heavy(n - 1);
}Använd en ackumulator
Genom att skicka en löpande totalsumma som ackumulator hålls varje stackram liten och rekursionen får formen av svansrekursion.
Vissa kompilatorer kan då återanvända en enda stackram.
#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;
}En säkerhetschecklista
Innan du litar på en rekursiv funktion bör du kontrollera:
1. Finns det ett basfall?
2. Kommer varje anrop närmare det?
3. Kan djupet bli mycket stort vid stora indata?
Om djupet kan öka kraftigt bör du använda en loop i stället.
Testa med små indata
Testa alltid rekursion först med mycket små indata som du kan verifiera för hand.
Om de små fallen fungerar och djupet förblir begränsat kan du skala upp med större säkerhet.
Snabbkontroll
Identifiera den säkraste lösningen.
Sammanfattning
Stack overflow uppstår när rekursionen blir för djup eller aldrig avslutas. Ange alltid ett nåbart basfall, minska argumentet vid varje anrop, håll stackramarna små och byt till iteration när djupet kan växa med indatans storlek.
Lär dig C med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 39
- Lektioner
- 144
Vanliga frågor
Är lektionen ”Undvik stack overflow” gratis?
Ja – hela texten till ”Undvik stack overflow” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i C Academy, kan Ni uppgradera till CoddyKit PRO. Kursen i C Academy innehåller totalt 4 lektioner.
Vad lär jag mig i ”Undvik stack overflow”?
Begränsa rekursionen. Ni övar på C Academy med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig C Academy?
Du behöver inga förkunskaper. Utbildningen i C Academy på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 4 av 4.
Hur lång tid tar lektionen ”Undvik stack overflow”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här C Academy-lektionen?
Ja. Varje C Academy-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Så fungerar rekursion
- Klassiska rekursiva problem
- Rekursion kontra iteration
- Undvik stack overflow