Переполнение стека

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

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

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

int foo() {     return foo();}

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

Это рафинированный пример, и в реальном коде на вопрос «хотел ли программист рекурсию?» возможны оба ответа.

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

Рекурсия требует очень аккуратного программирования, не зря рекурсивные переборы любили в спортивном программировании в 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)}

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

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

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 рекурсия может случиться, если в обработчике, например, изменения поля программист сам же это поле и изменит.

Здесь ответ — «хотел, но не понимал принцип действия». Блогер приводит код, приводящий к переполнению, если система так и не восстановилась:^[5]

void initializeApp() {    if (!systemIsHealthy())        recoverSystem();}void recoverSystem() {    initializeApp();}

В обходе сетей нередка ошибка^[6], псевдокод:

void Mesh::traverse(Triangle* triangle) {  if (!triangle || !triangle->isMarked())    return;  triangle->mark();  for (int i = 0; i < 3; ++i) {    traverse(triangle->neighbor(i));  }}

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

Также примером будет Introsort — если рекурсия зашла глубоко, он применяет другой алгоритм сортировки.

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

Пример на Си:

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

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

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

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