переповнення стека

У програмному забезпеченні переповнення стека (англ. Stack overflow) виникає, коли в стеці викликів зберігається більше інформації, ніж він може тримати. Зазвичай ємність стека задається при старті програми / потоку. Коли покажчик стека виходить за межі, програма аварійно завершує роботу. [1]

Ця помилка трапляється з трьох причин. [2]

Найпростіший приклад нескінченної рекурсії на Сі:

Функція буде викликати сама себе, витрачаючи простір в стеці, поки стік не переповниться і не трапиться помилка сегментації. [3]

Це рафінований приклад, і в реальному коді нескінченна рекурсія може з'явитися з двох причин:

Чи не спрацювало умова виходу з рекурсії

Часта причина переповнення стека - коли при якихось крайніх неперевірених обставин умова закінчення рекурсії взагалі не спрацює.

Програма піде в нескінченну рекурсію при негативному n.

Багато мови роблять оптимізацію, іменовану «хвостова рекурсія». Рекурсія, що знаходиться в кінці функції, перетворюється в цикл і не витрачає стека [4]. Якщо така оптимізація спрацює, замість переповнення стека буде зациклення.

Програміст написав рекурсию, не усвідомлюючи того

Програміст може написати рекурсию і ненавмисно - наприклад, коли одну і ту ж функціональність виконують кілька перевантажених функцій, і одна викликає іншу.

У інтерфейсних фреймворками зразок Qt і VCL рекурсія може статися, якщо в обробнику, наприклад, зміни поля програміст сам же це поле і змінить.

Дуже глибока рекурсія

Знищити однозв'язний список можна таким кодом:

Цей алгоритм, якщо перелік не зіпсований, теоретично виконається за кінцевий час, зажадавши при цьому O (n) стека. Зрозуміло, при довгому списку програма відмовить. Можливі рішення:

• Знайти нерекурсивний алгоритм (чудово працює в даному прикладі).
• Перенести рекурсию з системного стека в динамічно виділяється (наприклад, при обході різного роду мереж [5]).
• Якщо рекурсія зайшла глибоко, застосовувати інший метод. Наприклад, швидке сортування - надзвичайно ефективний метод сортування, який в крайніх випадках може задіяти чималий обсяг стека. Тому реалізації сортування в мовах програмування обмежують глибину рекурсії, а якщо «вперлися» в межа, використовують більш повільні методи на кшталт пірамідальної. Так працює, наприклад, Introsort.

Великі змінні в стеку

Масив займає 8 мегабайт пам'яті; якщо в стеці немає такої кількості пам'яті, трапиться переповнення.

Все, що зменшує ефективний розмір стека, збільшує ризик переповнення. Наприклад, потоки зазвичай беруть стека менше, ніж основна програма - тому програма може працювати в однопоточном режимі і відмовляти в багатопотоковому. Працюючі в режимі ядра підпрограми часто користуються чужим стеком, тому при програмуванні в режимі ядра намагаються не застосовувати рекурсію і великі локальні змінні. [7] [8]