Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

Из Википедии — свободной энциклопедии

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

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

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

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) стека. Разумеется, при длинном списке программа откажет. Возможные решения:

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

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

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

Пример на Си:

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

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

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

См. также

Примечания

  1. Burley, James Craig Using and Porting GNU Fortran (1 июня 1991). Дата обращения: 30 марта 2012. Архивировано из оригинала 5 октября 2012 года.
  2. Danny, Kalev Understanding Stack Overflow (5 сентября 2000). Дата обращения: 30 марта 2012. Архивировано 27 сентября 2020 года.
  3. What is the difference between a segmentation fault and a stack overflow? Архивная копия от 9 марта 2012 на Wayback Machine at StackOverflow
  4. An Introduction to Scheme and its Implementation (19 февраля 1997). Дата обращения: 30 марта 2012. Архивировано из оригинала 23 августа 2000 года.
  5. Пример ошибки (Архивная копия от 13 ноября 2020 на Wayback Machine) в poly2tri, известной библиотеке для построения ограниченной триангуляции Делоне многоугольника; ошибку исправили динамическим стеком STL.
  6. Feldman, Howard Modern Memory Management, Part 2 (23 ноября 2005). Дата обращения: 30 марта 2012. Архивировано 5 октября 2012 года.
  7. Kernel Programming Guide: Performance and Stability Tips. Apple Inc. (7 ноября 2006). Дата обращения: 30 сентября 2017. Архивировано 7 декабря 2008 года.
  8. Dunlap, Randy Linux Kernel Development: Getting Started (19 мая 2005). Дата обращения: 30 марта 2012. Архивировано из оригинала 5 октября 2012 года.
Эта страница в последний раз была отредактирована 15 октября 2023 в 21:12.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).