I mjukvara uppstår ett stackspill när det finns mer information lagrad på samtalsstacken än den kan hålla. Vanligtvis ställs stackkapaciteten vid program-/trådstart. När stackpekaren går utanför gränserna kraschar programmet. [ett]
Detta fel uppstår av tre anledningar. [2]
Det enklaste exemplet på oändlig rekursion i C :
int foo () { return foo (); }Funktionen anropar sig själv och tar utrymme på stacken tills stacken svämmar över och ett segmenteringsfel uppstår . [3]
Detta är ett förfinat exempel, och i verklig kod kan oändlig rekursion uppträda av två anledningar:
En vanlig orsak till oändlig rekursion är när, under vissa extrema oprövade omständigheter, rekursionsavbrottsvillkoret inte fungerar alls.
int factorial ( int n ) { om ( n == 0 ) retur 1 ; returnera n * faktoriell ( n - 1 ); }Programmet kommer att gå in i djup (4 miljarder samtal) rekursion om n är negativ .
Många språk gör en optimering som kallas " svansrekursion ". Rekursionen i slutet av funktionen förvandlas till en loop och förbrukar inte stacken [4] . Om en sådan optimering fungerar blir det en loop istället för en stack overflow .
En programmerare kan skriva rekursion oavsiktligt, till exempel när flera överbelastade funktioner utför samma funktionalitet, och en anropar en annan.
int Obj::getData ( int index , bool & isChangeable ) { isChangeable = sant ; return getData ( index ); } int Obj::getData ( int index ) { bool noMatter ; return getData ( index , noMatter ); }Se även Ond cirkel , Sepulki .
I gränssnittsramverk som Qt och VCL kan rekursion inträffa om till exempel en fältändringshanterare ändrar själva fältet.
Du kan förstöra en enskilt länkad lista med följande kod:
void destroyList ( struct Item * it ) { if ( it == NULL ) återvända ; destroyList ( it -> nästa ); gratis ( it ); }Denna algoritm, om listan inte är skadad, kommer teoretiskt att köras i ändlig tid, vilket kräver O( n ) i stacken. Naturligtvis, med en lång lista kommer programmet att misslyckas. Möjliga lösningar:
Den tredje stora anledningen till stackoverflows är engångsallokeringen av enorma mängder minne av stora lokala variabler. Många författare rekommenderar att allokera minne som är större än några kilobyte på " högen " snarare än på högen. [6]
Exempel i C :
int foo () { dubbel x [ 1000000 ]; }Arrayen upptar 8 megabyte minne; om det inte finns tillräckligt med minne i stacken kommer ett spill att inträffa.
Allt som minskar den effektiva stackstorleken ökar risken för översvämning. Trådar tar vanligtvis mindre stack än huvudprogrammet - så programmet kan fungera i enkeltrådsläge och misslyckas i flertrådsläge. Subrutiner som körs i kärnläge använder ofta någon annans stack, så när de programmerar i kärnläge försöker de att inte använda rekursion och stora lokala variabler. [7] [8]