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

[Brendan]

Частая причина переполнения стека — когда при каких-то крайних непроверенных обстоятельствах условие окончания рекурсии вообще не сработает. Простейший пример бесконечной рекурсии на C+.

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

int foo() {
     return foo();
}

Очень глубокая рекурсия.
Уничтожить односвязный список можно таким кодом:

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

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

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

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

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

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

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

Пример на языке Pawn:

Спойлер

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

stock SomeFunc() { 
    return SomeFunc(); 
}

Переполнение стека может еще быть из-за того, что некоторые стараются возвратить строку.

stock SomeFunc(text[]) { 
    return text; 
}

Это переполнение происходит из-за того, что массив не удаляется из памяти сервера, то есть ее забивает. Глобальные массивы и массивы, объявленные через static, из памяти не удаляется.

SomeFunc() { 
    // создали переменную она займет 4 байта 
    new i; 
    static j; 
     
    // всякие операции с ними 

    // переменная i удалена > освободили немного памяти 
    // переменная j не удалена > сколько было на нее затрачено, столько и осталось  
}

Автор сообщения: Dead_Moroz