В программном обеспечении переполнение стека ( англ. stack overflow) возникает, когда в стеке вызовов хранится больше информации, чем он может вместить. Обычно ёмкость стека задаётся при старте программы/потока. Когда указатель стека выходит за границы, программа аварийно завершает работу.

Эта ошибка случается по трём причинам.

Бесконечная рекурсия

Простейший пример бесконечной рекурсии на Си :

int foo() { return foo(); } 

Функция будет вызывать сама себя, расходуя пространство в стеке, пока стек не переполнится и не случится ошибка сегментации .

Это рафинированный пример, и в реальном коде бесконечная рекурсия может появиться по двум причинам:

Ошибки в намеренной рекурсии

Рекурсия требует очень аккуратного программирования, не зря рекурсивные переборы любили в спортивном программировании в 1990-е, пока защищённый режим (а значит, большие массивы) и стандартные библиотеки алгоритмов вроде STL не расширили ассортимент задач. Вот несколько ошибок.

Ошибка в условии окончания рекурсии:

int factorial (int n) { if (n == 1) // глубокая (4 млрд) рекурсия при n⩽0 return 1; return n * factorial(n - 1); } 

Ошибка в рекурсивном спуске:

int factorial (int n) { if (n <= 1) // условие верное… return 1; return n * factorial(n); // …а спуск неверный, надо (n - 1) } 

Многие компиляторы делают оптимизацию, именуемую « хвостовая рекурсия ». Рекурсия, находящаяся в конце функции, превращается в цикл и не расходует стека . Если такая оптимизация сработает, вместо переполнения стека будет зацикливание .

Программист написал рекурсию, не осознавая того

Программист может написать рекурсию и ненамеренно — например, когда одну и ту же функциональность выполняют несколько перегруженных функций, и одна вызывает другую.

int Obj::getData(int index, bool& isChangeable) { isChangeable = true; return getData(index); } int Obj::getData(int index) { bool noMatter; return getData(index, noMatter); } 

См. также Порочный круг , Сепульки .

Другой вариант — программист взял не ту перегрузку.

int Obj::getData(int index, bool& isChangeable) { ... } int Obj::getData(int index) { return getData(index); // случайно вызвал себя же } 

В интерфейсных фреймворках наподобие Qt и VCL рекурсия может случиться, если в обработчике, например, изменения поля программист сам же это поле и изменит.

Очень глубокая рекурсия

Уничтожить односвязный список можно таким кодом:

void destroyList(struct Item* it) { if (it == NULL) return; destroyList(it->next); free(it); } 

Этот алгоритм, если список не испорчен, теоретически выполнится за конечное время, затребовав при этом O( n ) стека. Разумеется, при длинном списке программа откажет. Возможные решения:

• Найти нерекурсивный алгоритм (работает в данном примере).
• Перенести рекурсию из аппаратного стека в динамически выделяемый (например, при обходе разного рода сетей ).
• Если рекурсия зашла глубоко, применять другой метод. Например, быстрая сортировка — чрезвычайно эффективный метод сортировки, который в крайних случаях может задействовать немалый объём стека. Поэтому реализации сортировки в языках программирования ограничивают глубину рекурсии, а если «упёрлись» в предел, используют более медленные методы наподобие пирамидальной . Так работает, например, Introsort .

Большие переменные в стеке

Третья большая причина переполнения стека — одноразовое выделение огромного количества памяти крупными локальными переменными. Многие авторы рекомендуют выделять память, превышающую несколько килобайт, в « куче », а не на стеке.

Пример на Си :

int foo() { double x[1000000]; } 

Массив занимает 8 мегабайт памяти; если в стеке нет такого количества памяти, случится переполнение.

Всё, что уменьшает эффективный размер стека, увеличивает риск переполнения. Потоки обычно берут стека меньше, чем основная программа — поэтому программа может работать в однопоточном режиме и отказывать в многопоточном. Работающие в режиме ядра подпрограммы часто пользуются чужим стеком, поэтому при программировании в режиме ядра стараются не применять рекурсию и большие локальные переменные.

См. также

• Переполнение буфера
• Стек вызовов
• Ошибка на единицу

Примечания