Рекурсия в задании №16 ЕГЭ по информатике: как решать без ошибок (с примерами Фибоначчи)

** изображение создано или обработано с помощью ИИ.

Рекурсия в задании №16 ЕГЭ проверяется через вычисление значений функций или подсчёт количества вызовов/выводов. Числа Фибоначчи — классический пример, но алгоритм решения универсален. Чтобы решить задачу за 3-4 минуты, достаточно выписать базовые случаи, построить трассировочное дерево или применить мемоизацию.

Ниже — пошаговый разбор типовых задач ФИПИ, готовые шаблоны кода на Python и лайфхаки для черновика. Все примеры сверены с демоверсией и кодификатором 2025–2026.

Как появилось это математическое чудо и почему о нем помнят программисты

** изображение создано или обработано с помощью ИИ.

Числа Фибоначчи — последовательность, в которой каждый следующий член равен сумме двух предыдущих, обычно начинается с 0 и 1. В задачах ЕГЭ по информатике эта последовательность используется для тренировки вычислительного мышления: умения видеть зависимость от предыдущих шагов, понимать рекурсивные алгоритмы и правильно организовывать циклы.

На ЕГЭ значения n в задачах на рекурсию небольшие (обычно до 20-30). Главная задача — не запутаться в порядке вычислений и правильно отследить базовые случаи. Типовые формулировки:

1. F(n) = n + F(n-2) при n > 2, F(1) = 1, F(2) = 2.

1. F(n) = 2*F(n-1) + n при n > 1, F(1) = 1.

Алгоритм решения всегда один: выписать базовые случаи → применить рекуррентную формулу → вычислить значение вручную или запустить код с мемоизацией.

Числа Фибоначчи в ЕГЭ: рекурсия и цикл в задании №16

** изображение создано или обработано с помощью ИИ.

Рекурсивная реализация вычисления чисел Фибоначчи — fib(n) = fib(n-1) + fib(n-2) выглядит кратко. Но для больших n (например, 40 и выше) работает неприемлемо долго. Каждый вызов порождает два новых, что приводит к экспоненциальному росту числа операций и значительным затратам памяти под стек вызовов.

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

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

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

Применение в структуре данных и кодировании

** изображение создано или обработано с помощью ИИ.

Где ещё пригодится рекурсия на ЕГЭ? Рекурсивное мышление, которое тренируется на числах Фибоначчи, полезно не только для задания №16. Оно напрямую помогает во второй части экзамена:

1. Задание №27 (динамическое программирование). Многие задачи решаются через перебор состояний с запоминанием промежуточных результатов. Понимание мемоизации экономит до 10 минут на экзамене.

1. Задания №24 и №25 (обработка строк и массивов). Когда результат текущего шага зависит от предыдущих, рекурсивная логика помогает быстро выстроить цепочку вычислений без «велосипедов» в коде.

1. Отладка программ. Если код падает или выдаёт неверный ответ, трассировка по принципу дерева вызовов позволяет найти ошибку за 1-2 минуты, а не переписывать программу с нуля.

На ЕГЭ это не абстрактная теория, а рабочий инструмент для чистого кода и стабильных баллов во второй части.

Типичные ошибки в задании №16 ЕГЭ по рекурсии

** изображение создано или обработано с помощью ИИ.

При решении задач на рекурсивные функции в ЕГЭ по информатике встречаются три типичные технические ошибки.

Первая — путаница с началом отсчёта (сдвиг индексации). В условии задаются базовые случаи для конкретных значений аргумента, например F(1)=1, F(2)=1. Ученик может по привычке начать отсчёт с нуля (F(0)=1) или перепутать, какое значение соответствует какому номеру вызова.

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

Вторая — отсутствие условия остановки рекурсии. В теле рекурсивной функции обязательно должно быть ветвление, которое прерывает дальнейшие вызовы при достижении базовых значений (например, if n <= 2: return …).

Если это условие пропущено или записано неверно (например, n == 0 вместо n <= 2 для случая, где базовые значения заданы для 1 и 2), рекурсия не завершится. Программа вызовет саму себя бесконечно, что приведёт к ошибке переполнения стека (RecursionError).

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

Третья — ошибка в подсчёте количества вызовов или выводимых значений. В некоторых заданиях требуется не вычислить значение функции, а определить, сколько раз функция была вызвана (или сколько значений она напечатала) в процессе рекурсивных вычислений. Удерживать всё дерево вызовов в уме при n больше 4–5 затруднительно.

Полезные приёмы:

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

1. Использовать известное соотношение: для стандартной рекурсивной реализации чисел Фибоначчи (F(n) = F(n-1) + F(n-2) с двумя базовыми случаями) общее количество вызовов равно 2·F(n) — 1. Для других рекуррентных формул это соотношение не работает, но можно вывести похожее, если внимательно проанализировать структуру вызовов.

1. Применять метод трассировки на малых n (например, от 1 до 5), чтобы увидеть закономерность, а затем экстраполировать её для нужного n.

Эти ошибки носят технический, а не логический характер, но на экзамене они приводят к потере времени на отладку и могут стоить баллов.

Систематическая тренировка ручной трассировки рекурсии на небольших значениях n помогает выработать внимательность и снизить риск таких сбоев.

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

Неожиданная история о том, как Фибоначчи спасла

** изображение создано или обработано с помощью ИИ.

На одном из пробников ученик получил задачу №16: вычислить значение функции при n = 15. Он начал считать «в уме», но запутался в ветвлениях, потратил 7 минут и получил неверный ответ.

Вспомнив принцип чисел Фибоначчи, он быстро нарисовал таблицу вызовов. Заметил повторяющиеся подзадачи и применил мемоизацию прямо на черновике. Результат пересчитал за 2 минуты без ошибок и забрал балл.

Этот случай показывает главное правило экзамена: не считайте вслепую, а структурируйте вызовы. Трассировка на бумаге + запоминание повторяющихся значений = гарантия выполнения задания №16 даже при ограниченном времени.

Как эффективно готовиться к заданиям про Фибоначчи на ЕГЭ

** изображение создано или обработано с помощью ИИ.

1. Вычислите F(1)…F(10) на бумаге, чтобы закрепить базовые случаи.

1. Реализуйте функцию двумя способами: итеративным (цикл for) и рекурсивным с @lru_cache или словарём. Сравните время выполнения на n = 15-20 — это диапазон, характерный для заданий ЕГЭ.

1. На экзамене добавляйте комментарии к базовому случаю и рекуррентному шагу — это снижает риск логических ошибок при проверке.

Готовый шаблон трассировки и чек-лист отладки рекурсивных функций есть в онлайн-школе. Проверьте, готовы ли вы к заданию.