В программном обеспечении переполнение стека () возникает, когда в стеке вызовов хранится больше информации, чем он может вместить. Обычно ёмкость стека задаётся при старте программы/потока. Когда указатель стека выходит за границы, программа аварийно завершает работу.
Эта ошибка случается по трём причинам.
Бесконечная и условно-бесконечная рекурсия Простейший пример бесконечной рекурсии на Си: int foo() { return foo(); }
Функция будет вызывать сама себя, расходуя пространство в стеке, пока стек не переполнится и не случится ошибка сегментации.What is the difference between a segmentation fault and a stack overflow? at StackOverflow
Это рафинированный пример, и в реальном коде на вопрос «хотел ли программист рекурсию?» возможны оба ответа.
Помимо действительно бесконечной рекурсии, бывает такая, которая остановится на неопределённой глубине или по арифметическому переполнению — назовём её условно-бесконечной.
Ошибки в намеренной рекурсии Рекурсия требует очень аккуратного программирования, не зря рекурсивные переборы любили в спортивном программировании в 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); }
См. также Порочный круг, Сепульки.
В интерфейсных фреймворках наподобие Qt и VCL рекурсия может случиться, если в обработчике, например, изменения поля программист сам же это поле и изменит (скажем, чтобы привести в допустимое значение).
Рекурсия вместо цикла Здесь ответ — «хотел, но не понимал принцип действия». Блогер приводит код, приводящий к переполнению, если система так и не восстановилась:https://blog.devops.dev/the-hidden-recursion-trap-why-your-utility-function-might-crash-production-at-2-am-56854987554f void initializeApp() { if (!systemIsHealthy()) recoverSystem(); }
void recoverSystem() { initializeApp(); }
Очень глубокая рекурсия В обходе сетей нередка ошибкаПример ошибки () в poly2tri, известной библиотеке для построения ограниченной триангуляции Делоне многоугольника; ошибку исправили динамическим стеком STL., псевдокод: void Mesh::traverse(Triangle* triangle) { if (!triangle || triangle->isMarked()) return; triangle->mark(); for (int i = 0; i < 3; ++i) { traverse(triangle->neighbor(i));
Здесь глубина рекурсии очевидно ограничена сверху, и проблема в том, что стек исчерпается раньше, чем ёмкость памяти на сеть. Ошибку исправили переносом стека из аппаратного в динамически выделяемый.
Также примером будет Introsort — если рекурсия зашла глубоко, он применяет другой алгоритм сортировки.
Большие переменные в стеке Третья большая причина переполнения стека — одноразовое выделение огромного количества памяти крупными локальными переменными. Многие авторы рекомендуют выделять память, превышающую несколько килобайт, в «куче», а не на стеке.
Пример на Си: int foo() { double x[1000000]; }
Массив занимает 8 мегабайт памяти; если в стеке нет такого количества памяти, случится переполнение.
Всё, что уменьшает эффективный размер стека, увеличивает риск переполнения. Потоки обычно заводят меньший стек, чем основная программа — поэтому программа может работать в однопоточном режиме и отказывать в многопоточном. Работающие в режиме ядра подпрограммы часто пользуются чужим стеком, поэтому при программировании в режиме ядра стараются не применять рекурсию и большие локальные переменные.
См. также Переполнение буфера Стек вызовов Переполнение памяти Ошибка на единицу
Примечания
Категория:Ошибки программирования Категория:Стек