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

Эта статья — о компьютерной ошибке. О сайте для программистов см. Stack Overflow.

В программном обеспечении переполнение стека (англ. 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);
}

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

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

Рекурсия вместо цикла

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

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

void recoverSystem() {
    initializeApp();
}

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

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

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

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

См. также

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