Рекуррентное мышление: база, переход и стек вызовов

Автор: Казачкин Даниил Михайлович · Обновлено 23 августа 2026 г.

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

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

У рекурсивного решения всегда должны быть две части:

1. Базовый случай, где функция больше не вызывает себя.
2. Рекурсивный шаг, где задача уменьшается.

Пример с факториалом

Факториал числа n — это произведение чисел от 1 до n.

def factorial(n):
    if n == 0:
        return 1

    return n * factorial(n - 1)

print(factorial(5))

Базовый случай — n == 0. Без него функция вызывала бы себя бесконечно.

Как читать рекурсию

Не пытайтесь раскрывать сразу все вызовы в голове. Сначала проверьте базовый случай. Затем убедитесь, что каждый шаг приближает к нему. После этого разберите маленький пример: factorial(3) вызывает factorial(2), затем factorial(1), затем factorial(0).

Рекурсия и циклы

Многие рекурсивные задачи можно решить циклом. Например, сумму чисел от 1 до n проще записать через for. Рекурсия полезнее там, где структура задачи сама разветвляется: дерево вариантов, обход файлов, перебор ходов, разбор выражения.

Частые ошибки

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

Для школьника рекурсия важна не только как прием кодирования. Она учит видеть задачу через повторяющуюся структуру: решить маленькую часть и передать похожую работу следующему вызову.

Практикум: лестница и рекуррентное состояние

Ученик поднимается на 1 или 2 ступени. Обозначьте ways[n] как число способов попасть ровно на ступень n. Выпишите ответы для 0, 1, 2, 3 и 4 вручную, затем сформулируйте переход из двух предыдущих состояний. Реализуйте таблицу снизу вверх и отдельно нарисуйте дерево рекурсивных вызовов для n = 5. Сравните число повторно решаемых подзадач. Проверьте договорённость для нулевой ступени и отклонение отрицательного номера — без базы рекуррентная формула неполна.

Контрольная точка

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

Частые вопросы

Рекуррентная формула обязательно означает рекурсивную функцию?

Нет. Формула описывает зависимость состояний. Её можно вычислить рекурсией, таблицей динамического программирования или несколькими переменными. Реализация выбирается с учётом повторов, памяти и глубины вызовов.