V softwaru dochází k přetečení zásobníku , když je v zásobníku volání uloženo více informací, než může pojmout. Kapacita zásobníku se obvykle nastavuje na začátku programu/vlákna. Když ukazatel zásobníku překročí hranice, program se zhroutí. [jeden]
K této chybě dochází ze tří důvodů. [2]
Nejjednodušší příklad nekonečné rekurze v C :
int foo () { návrat foo (); }Funkce bude volat sama sebe a zabírat místo v zásobníku, dokud zásobník nepřeteče a nedojde k chybě segmentace . [3]
Toto je rafinovaný příklad a ve skutečném kódu se nekonečná rekurze může objevit ze dvou důvodů:
Častou příčinou nekonečné rekurze je situace, kdy za některých extrémních nevyzkoušených okolností podmínka ukončení rekurze nebude fungovat vůbec.
int faktoriál ( int n ) { if ( n == 0 ) návrat 1 ; návrat n * faktoriál ( n - 1 ); }Pokud je n záporné , program přejde do hluboké (4 miliardy hovorů) rekurze .
Mnoho jazyků provádí optimalizaci zvanou „ tailová rekurze “. Rekurze na konci funkce se změní na smyčku a nespotřebovává zásobník [4] . Pokud taková optimalizace funguje, místo přetečení zásobníku bude smyčka .
Programátor může napsat rekurzi neúmyslně, například když několik přetížených funkcí provádí stejnou funkci a jedna volá jinou.
int Obj::getData ( int index , bool & isChangeable ) { isChangeable = true ; return getData ( index ); } int Obj::getData ( int index ) { bool noMatter ; return getData ( index , noMatter ); }Viz také Bludný kruh , Sepulki .
V rozhraních, jako jsou Qt a VCL , může k rekurzi dojít, pokud například obslužný program změny pole změní samotné pole.
Jednotlivě propojený seznam můžete zničit pomocí následujícího kódu:
void zničitList ( struct Item * it ) { if ( it == NULL ) vrátit se ; zničitList ( it -> další ); zdarma ( to ); }Tento algoritmus, pokud není seznam poškozen, teoreticky poběží v konečném čase a vyžaduje O( n ) zásobníku. Samozřejmě s dlouhým seznamem program selže. Možné řešení:
Třetím velkým důvodem přetečení zásobníku je jednorázová alokace obrovského množství paměti velkými lokálními proměnnými. Mnoho autorů doporučuje alokovat paměť větší než několik kilobajtů na " hromadě " spíše než na zásobníku. [6]
Příklad v C :
int foo () { double x [ 1000000 ]; }Pole zabírá 8 megabajtů paměti; pokud na zásobníku není dostatek paměti, dojde k přetečení.
Cokoli, co snižuje efektivní velikost zásobníku, zvyšuje riziko přetečení. Vlákna obvykle zabírají méně zásobníku než hlavní program – program tedy může pracovat v režimu s jedním vláknem a selhat ve vícevláknovém režimu. Podprogramy běžící v režimu jádra často používají zásobník někoho jiného, takže při programování v režimu jádra se snaží nepoužívat rekurzi a velké lokální proměnné. [7] [8]