ЕГЭ информатика: рекурсия просто

ЕГЭ информатика: рекурсия просто, без тумана

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

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

Хорошая новость: в ЕГЭ рекурсия проверяет не гениальность, а аккуратность. Нужно ответить на два вопроса: когда функция остановится? И что она вернёт (или напечатает) на каждом шаге? Если ответить на них спокойно, задача перестаёт быть страшной.

Матрешка — вы открываете одну, внутри другая. Потом ещё одну. Но рано или поздно попадается самая маленькая. Это и есть базовый случай (условие выхода). Без него рекурсия становится бесконечным зацикливанием. Компьютер такое не любит. Ученик — особенно в мае.

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

Пример из занятий:

— Я запутался уже на третьем вызове.

— Значит, пора рисовать таблицу.

— А без таблицы?

— Можно. Но зачем страдать бесплатно?

Что такое рекурсия на языке нормальных людей

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

Рекурсия — это вызов функции из самой себя. Не ради красоты, а для разбиения исходной задачи на более мелкие копии. Так считают факториал, обходят деревья, перебирают варианты. В ЕГЭ чаще дают простые числовые функции.

Пример. Функция F(n). При n > 1 возвращает F(n–1) + n. При n = 1 возвращает 1. Вызов F(4) зависит от F(3). F(3) — от F(2). F(2) — от F(1). Базовый случай найден, цепочка идёт обратно. Шаги:

1. F(1) = 1.

1. F(2) = 1 + 2 = 3.

1. F(3) = 3 + 3 = 6.

1. F(4) = 6 + 4 = 10.

Никакой мистики. Просто очередь долгов, которые функция возвращает наверх.

Два направления. Сначала спуск к базовому случаю. Затем подъём к ответу. Многие теряются, потому что видят только спуск — пишут вызовы вниз и забывают вернуться. А именно на подъёме рождается итоговое значение.

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

Если нужна система, а не хаос — посмотрите курс подготовки к ЕГЭ по информатике в онлайн-формате. Курс даёт структуру, расписание и обратную связь. Вы перестаёте гадать, где в рекурсии подъём, и начинаете уверенно решать задачи.

Как читать рекурсивный код на ЕГЭ

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

Начинайте не с вычислений, а с поиска точки остановки. Найдите условие, при котором функция перестаёт вызывать себя. Обычно это n меньше или равно какому-то значению. Иногда базовый случай спрятан в ветке if. Подчеркните его в черновике — экзамен не проверяет каллиграфию.

Затем посмотрите, как меняется аргумент при каждом вызове. Уменьшается на 1? Делится на 2? Бывает, что функция вызывает себя дважды: F(n–1) и F(n–2). Тогда дерево вызовов растёт быстрее, и особенно полезна таблица значений.

Порядок действий, который я советую:

1. Найти базовый случай (условие выхода).

1. Записать стартовый вызов.

1. Определить, как меняется аргумент.

1. Нарисовать цепочку вызовов или заполнить таблицу.

1. Отдельно отметить команды вывода (print), если они есть.

1. Вернуться назад по цепочке и вычислить итог.

Если функция возвращает значение — записывайте промежуточный результат рядом с каждым вызовом. Например: F(3) = ? Затем заменяйте вопросительный знак на число.

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

Типичная причина ошибки. Ученик говорит: «Я понял смысл, но ответ другой». Почти всегда дело в одной строке: команда стоит до рекурсивного вызова, а не после. Или в условии используется строгое неравенство (<), а не ≤. Такие знаки выглядят мелкими, но именно они определяют весь результат.

Таблица вызовов: спасательный круг для черновика

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

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

Для функций, которые возвращают значение — три колонки: вызов, что нужно узнать, ответ. Пример: F(n) = F(n-1) + 2 при n > 1. F(1) — базовое значение. F(2) опирается на F(1). F(3) — на F(2). Таблица раскладывает всё по полочкам.

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

Моя мини-инструкция для учеников:

1. Не сокращайте запись слишком рано.

1. Каждый вызов пишите с конкретным аргументом.

1. Базовый случай обводите, чтобы видеть остановку.

1. Вывод на экран записывайте в отдельную строку.

1. После получения ответа перечитайте условие задачи ещё раз.

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

Правило «одна мысль — одна строка». Увидели вызов — записали. Получили значение — поставили рядом. Переходите назад — не прыгайте через ступеньки. На первых тренировках это медленнее. Но потом рука сама ведёт черновик.

Типичные ошибки и как их поймать заранее

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

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

Вторая ошибка — перепутать print и return. Print выводит на экран. Return возвращает значение в точку вызова. Если функция не возвращает ничего явно, Python возвращает None. На экзамене это важно, когда код приближен к реальному Python.

Третья ошибка — неверный порядок вывода. Смотрите на расположение команды. До рекурсивного вызова — печать при движении вниз. После него — печать при движении вверх. Если вызовов два, порядок становится ещё сложнее. Без схемы лучше не пытаться.

Четвёртая ошибка — игнорировать ветвления. В коде может быть if для чётных и нечётных чисел. Нельзя считать по одной привычной формуле. Сначала проверьте условие для текущего n, затем выбирайте нужную ветку.

Пятая ошибка — считать «на глаз». Рекурсия не любит гадания. Она требует дисциплины. Черновик должен показывать путь к ответу. Если путь не виден — вы просто надеетесь. Надежда хороша в кино, в информатике лучше таблица.

Короткий список для самопроверки:

1. Проверьте знак в условии: <, >, ≤, ≥, =.

1. Отдельно отметьте базовое значение.

1. Не меняйте порядок строк кода в голове.

1. Следите за целочисленным делением, если оно есть.

1. Сравните вопрос задачи с тем, что вы посчитали.

Самая обидная ситуация: решение правильное, а ответ не тот. Почему? Человек нашёл F(10), а в задаче просили F(9). Стартовый вызов тоже стоит подчёркивать. Мелочь, но полезная.

Как тренироваться, чтобы рекурсия стала привычной

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

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

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

Примерный план на неделю:

1. День 1: базовый случай и цепочки вызовов (спуск).

1. День 2: return, вычисление возвращаемых значений.

1. День 3: print до рекурсивного вызова и после него.

1. День 4: два рекурсивных вызова.

1. День 5: ветвления по условию (if-else).

1. День 6: смешанные задачи (и return, и print).

1. День 7: повтор ошибок и мини-тест.

Три вопроса после каждой задачи. Где остановка (базовый случай)? Что происходит до рекурсивного вызова? Что происходит после него? Эти вопросы быстро становятся привычкой. А привычка на экзамене дороже вдохновения.

Если задача не идёт. Не бейтесь лбом десять минут. Разберите самый маленький пример. Вместо F(20) возьмите F(3). Посмотрите, как ведёт себя функция. Потом увеличьте аргумент. Рекурсия часто раскрывается на малых числах.

Не называйте себя «не математиком» после первой ошибки. Рекурсия действительно поначалу кажется странной. Но в ней есть ритм: найдите базу, спуститесь, вернитесь, запишите ответ. Повторите это несколько раз, и внезапно тот самый страшный код превратится в обычную задачу на внимательность.