ЕГЭ 2026 · Задание 16

Рекурсивные алгоритмы

Как разворачивать рекурсию, считать значения и не теряться в повторных вызовах.

Повышенный уровеньРекурсия25–35 мин✓ Полный урок

Что нужно понимать

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

База

Ветвь, которая возвращает значение без нового рекурсивного вызова.

↩

Переход

Формула связывает F(n) с F(n−1), F(n−2) и т.д.

memo

Таблица

Если значения повторно используются, записывайте их один раз — это динамика.

Ключевая идея

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

Надёжный алгоритм решения

Найди базовые случаи

Например F(1)=1.

Выпиши рекуррентную формулу

Что именно добавляется или умножается при переходе к n?

Считай по возрастанию n

F(2), F(3), … до нужного значения.

Для двух предыдущих значений

Храни сразу F(n−1) и F(n−2).

Проверь тип результата

Особенно при больших числах и целочисленном делении.

Типичная ошибка: Не подставляй F(n−1) в формулу «на глаз» несколько раз: записывай промежуточные значения, иначе легко потерять один вызов или коэффициент.

Пошаговый разбор

Задано F(1)=1, а при n>1: F(n)=F(n−1)+2n. Найдите F(4).

Считаем от базыИсходные данные

F(1)=1

F(2)=1+4=5; F(3)=5+6=11.

Последний шагРезультат

F(4)=11+8=19.

РазборОткрывай шаги по очереди

1 + 2·2 = 5.

5 + 2·3 = 11.

11 + 2·4 = 19.

Тренажёр

Ответь на оба вопроса. Проверка работает прямо в браузере; правильные ответы автоматически отмечают практику выполненной.

Практика

Закрепи алгоритм

2 вопроса

F(1)=1, F(n)=F(n−1)+n. Чему равно F(5)?

G(1)=1, G(2)=2, G(n)=G(n−1)+G(n−2). Чему равно G(6)?

Шпаргалка на экзамен

Всегда начинай с базовых случаев.
При вычислении значения двигайся снизу вверх.
Повторяющиеся значения сохраняй в таблицу.
Для F(n−1)+F(n−2) держи две предыдущие строки динамики.

Урок 16 завершён

Продолжай по маршруту

Прогресс урока сохраняется локально в браузере.

← Задание 15 Задание 17 →

Тематика урока сверена с актуальным каталогом ЕГЭ‑2026; примеры и тренажёры ТурбоУроки составлены самостоятельно. Каталог заданий ↗