C Academy · Урок

Как избежать переполнения стека

Ограничивайте глубину рекурсии.

«Как избежать переполнения стека» — бесплатный урок C Academy на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения C Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс C Academy содержит 4 уроков всего.

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

Стек вызовов имеет ограниченный размер. Каждый вызов функции использует его часть для параметров и локальных переменных.

Если рекурсия становится слишком глубокой, стек заполняется и программа завершается с ошибкой переполнения стека.

Отсутствующий базовый случай

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

Не запускайте такую функцию; разберите, почему она завершается с ошибкой.

int broken(int n) {
    /* no base case: never stops */
    return broken(n + 1);
}

Аргумент не приближается к завершению

Даже при наличии базового случая аргумент должен приближаться к нему. Здесь n увеличивается, поэтому оно никогда не достигает 0.

Всегда проверяйте, что каждый вызов приближает выполнение к условию остановки.

int oops(int n) {
    if (n == 0) return 0;
    return oops(n + 1); /* wrong direction */
}

Правильная версия

Если изменить направление, функция завершится. Теперь n уменьшается и приближается к базовому случаю 0.

#include <stdio.h>

int good(int n) {
    if (n == 0) return 0;
    return n + good(n - 1);
}

int main(void) {
    printf("%d\n", good(10));
    return 0;
}

Ограничения глубины существуют

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

При очень большой глубине предпочитайте итерацию.

Преобразуйте глубокую рекурсию в цикл

Если глубина рекурсии растёт вместе с размером входных данных, замените её циклом. Это избавит от накопления тысяч кадров.

Цикл ниже безопасно суммирует числа от 1 до большого n, используя постоянный объём памяти.

#include <stdio.h>

int main(void) {
    long total = 0;
    for (int i = 1; i <= 1000000; i++)
        total += i;
    printf("%ld\n", total);
    return 0;
}

Уменьшайте глубину делением задачи

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

long range_sum(int lo, int hi) {
    if (lo == hi) return lo;
    int mid = (lo + hi) / 2;
    return range_sum(lo, mid) + range_sum(mid + 1, hi);
}

Остерегайтесь больших локальных массивов

Локальные переменные Big делают каждый кадр heavy, поэтому стек заполняется быстрее.

Не объявляйте большие массивы внутри рекурсивной функции; вместо этого передавайте указатели или используйте кучу.

void heavy(int n) {
    int buffer[10000]; /* big frame each call */
    if (n == 0) return;
    heavy(n - 1);
}

Используйте аккумулятор

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

Тогда некоторые компиляторы могут повторно использовать один кадр.

#include <stdio.h>

long sum_acc(int n, long acc) {
    if (n == 0) return acc;
    return sum_acc(n - 1, acc + n);
}

int main(void) {
    printf("%ld\n", sum_acc(100, 0));
    return 0;
}

Проверка безопасности

Прежде чем полагаться на рекурсивную функцию, проверьте:

1. Есть ли базовый случай?
2. Приближает ли каждый вызов выполнение к нему?
3. Может ли глубина стать огромной при больших входных данных?

Если глубина может резко вырасти, используйте цикл.

Проверка на небольших входных данных

Всегда сначала проверяйте рекурсию на крошечных входных данных, результат которых можно вычислить вручную.

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

Быстрая проверка

Найдите самое безопасное исправление.

Итоги

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

Часто задаваемые вопросы

Урок «Как избежать переполнения стека» бесплатный?

Да — полный текст урока «Как избежать переполнения стека» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс C Academy, подпишись на CoddyKit PRO. Курс C Academy содержит 4 уроков всего.

Чему я научусь в уроке «Как избежать переполнения стека»?

Ограничивайте глубину рекурсии. Ты практикуешь C Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать C Academy?

Предыдущий опыт не требуется. C Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.

Сколько времени занимает урок «Как избежать переполнения стека»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке C Academy?

Да. Каждый урок C Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

← Назад к C Academy