Рекурсия и рекурсивные алгоритмы: разбор для ЕГЭ

Понятие рекурсии и базовый случай: учимся не уходить в бесконечность

Задание 16 на ЕГЭ по информатике кажется простым, пока функция не выдаёт ошибку переполнения стека или не зависает прямо на экзамене. В этой статье мы по шагам разберём механику рекурсивных алгоритмов, научимся обходить частые ловушки составителей и автоматизировать решения на Python.

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

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

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

Стек вызовов и глубина: почему падает программа

Каждый раз, когда функция совершает рекурсивный вызов, интерпретатор Python приостанавливает текущее вычисление. Он запоминает значения локальных переменных и адрес возврата в специальной области оперативной памяти — стеке вызовов (call stack).

Память стека организуется по правилу «последним пришёл — первым ушёл» (LIFO). Когда цепочка вызовов наконец достигает базового случая, стек начинает «сворачиваться» обратно: функция подставляет готовые числа в ожидающие выражения и отдаёт итоговый результат в точку первого запуска.

Управлять лимитом вызовов легко: добавь команду sys.setrecursionlimit(5000) в самое начало скрипта. Проверить своё понимание работы стека на практике можно в личном кабинете «Просто Урок», где интерактивный тренажёр сразу подсвечивает опасные места в коде.

Ручная трассировка: как просчитать алгоритм на черновике

В номерах с небольшими аргументами (например, поиск F(5) или F(6)) надёжнее и быстрее посчитать значение функции прямо на бумаге. Для этого используется трассировочная таблица: мы вычисляем значения последовательно снизу вверх — от известного базового случая к целевому числу.

Рассмотрим алгоритм, заданный соотношениями:
F(1) = 1;
F(n) = F(n - 1) + 2 · n, при n > 1.

Построим пошаговую таблицу вычислений для значений аргумента от n = 1 до n = 5:

Аргумент (n)	Формула перехода	Подстановка значений	Итог F(n)
1	Базовый случай	1	1
2	F(1) + 2 · 2	1 + 4	5
3	F(2) + 2 · 3	5 + 6	11
4	F(3) + 2 · 4	11 + 8	19
5	F(4) + 2 · 5	19 + 10	29

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

Разбор типового задания №16: пишем программный код

На реальном экзамене часто встречаются формулы с условиями чётности и большими числами. Разберём типовую задачу: алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

F(n) = 2 при n = 1;
F(n) = 3 · F(n - 1) + 1, если n > 1 и число n нечётно;
F(n) = F(n - 1) + n, если n > 1 и число n чётно.
Чему равно значение функции F(26)?

Перенесём математическое условие в программный код на языке Python:

def F(n):
\(     if n == 1: \)
        return 2
\(     if n \% 2 != 0: \)
\(         return 3 * F(n - 1) + 1 \)
\(     return F(n - 1) + n \)

print(F(26))

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

Мемоизация и ускорение: что делать при зависании алгоритма

Если в теле функции присутствуют два и более рекурсивных вызова (например, F(n - 1) + F(n - 2)), количество операций растёт экспоненциально со скоростью 2ⁿ. Уже при n = 40 программа потребует миллиарды операций и намертво зависнет.

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

import sys
from functools import lru_cache

sys.setrecursionlimit(5000)

@lru_cache(None)
def F(n):
\(     if n <= 2: \)
        return 1
\(     return F(n - 1) + 2 * F(n - 2) \)

print(F(400))

Декоратор @lru_cache(None) сохраняет ответ для каждого аргумента в хэш-таблице. Повторные обращения забирают готовое число за константное время O(1). Отработать технику кэширования на реальных прототипах ЕГЭ можно бесплатно через образовательную платформу.

Что запомнить для экзамена и план дальнейших действий

Для безошибочного выполнения задания 16 на ЕГЭ по информатике держи в голове ключевой чек-лист:

1. Всегда чётко формулируй базовый случай, чтобы исключить бесконечные циклы.
2. При вычислении больших номеров (n > 900) расширяй лимит вызовов через sys.setrecursionlimit().
3. Если функция ветвится на два и более вызова — обязательно подключай декоратор @lru_cache(None).
4. Внимательно проверяй операции целочисленного деления // и остатка % в теле условий.

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