С нуля до 90+: рекурсия просто в информатике ЕГЭ

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

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

Тема «Рекурсия просто» в контексте ЕГЭ по информатике звучит почти как шутка. Я тоже так думал. Мне 27, я несколько лет разбираю задания с ребятами и каждый май вижу одну картину: человек знает Python, решает таблицы, бодро щёлкает логику, но когда встречает функцию F(n), которая вызывает F(n‑1), его взгляд тухнет.

На самом деле рекурсия — не магия. Это функция, которая вызывает саму себя. Главное — она делает это не бесконечно: у неё есть условие остановки. Без остановки программа уходит в «яму», и компьютер, не грустя, просто падает с ошибкой.

Представьте лестницу. Вы стоите на ступеньке n. Рекурсивный вызов говорит: «спустись на ступеньку ниже». Так продолжается, пока не дойдёте до первой. Потом начинается обратный путь — на нём функция собирает ответ.

«То есть надо просто спуститься вниз и подняться обратно?» — спросит ученик. Да, именно. Звучит почти обидно просто. Но на ЕГЭ ловят не на идее рекурсии, а на внимательности, порядке действий и мелких условиях в коде.

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

Как читать рекурсивную функцию глазами экзамена

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

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

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

Найдите базовый случай — место, где функция не вызывает себя, и запишите его отдельно. Например, F(1) = 1. Посмотрите, как получить следующее значение. Считайте снизу вверх, если аргументы уменьшаются. Следите за целочисленным делением, остатком и условиями.

Пример: F(n) = F(n‑1) + n, а F(1) = 1. Тогда F(2) = 3, F(3) = 6, F(4) = 10 — это сумма чисел. Но не нужно сразу кричать «формула!»: сначала докажите себе пару шагов руками.

Иногда функция вызывает себя дважды, например F(n‑1) и F(n‑2). Здесь без таблицы легко ошибиться. Я сам однажды на занятии бодро посчитал F(5) двумя разными способами. Ученик заметил. Неловко? Да. Полезно? Еще бы.

Базовый случай и шаг: два замка одной двери

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

Базовый случай — это тормоз. Он говорит: «Хватит копать». Если его нет, рекурсия становится бесконечной. В реальной программе стек вызовов быстро переполняется, в школьной задаче ответ обычно становится невозможным.

Рекурсивный шаг — это движение к тормозу. Аргумент при этом чаще всего уменьшается, например n‑1, n//2 или n‑3. Если шаг уводит от базы, функция ломается. Это похоже на попытку добраться до холодильника через балкон соседа — иногда можно, но это странно и ненадёжно.

Проверяйте две вещи. Первая: достигнет ли аргумент базового случая? Вторая: что вернёт функция при возврате? Эти два вопроса снимают половину страха. Остальная половина лечится практикой и чаем.

Маленький пример. Пусть F(n) = 2 * F(n‑1) при n > 1, и F(1) = 3. Тогда F(2) = 6, F(3) = 12, F(4) = 24. Мы каждый раз умножаем предыдущее значение на 2.

А если база F(0), а спрашивают F(5)? Тогда вы стартуете с нуля, а не с единицы. Это частая ловушка. В условии нет декоративных деталей — каждая цифра там работает, даже если выглядит скучно.

Ещё один важный момент — порядок операций. В строке return F(n‑1) + F(n‑2) сначала нужно вычислить оба значения, и только потом их сложить. Функция не «понимает идею», а просто исполняет команды в том порядке, в котором они записаны.

Типовые сюжеты ЕГЭ, где рекурсия прячется в коде

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

На экзамене рекурсия обычно появляется в понятных «костюмах».

Первый — вычислить значение функции. Это самый прямой вариант: дан код, спрашивают F(8) или F(20). Здесь помогает таблица значений, которую вы заполняете последовательно.

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

Третий вариант — анализ алгоритма с условием. Например, при чётном n функция делит число на 2, при нечётном вычитает 1. Здесь важно идти по конкретной траектории, не считая лишние ветки.

Встречаются и задания про строки: функция берёт символ, обрезает строку и снова вызывает себя. Принцип тот же: сначала находите остановку, потом смотрите, когда добавляется символ — до вызова или после.

Если вы чувствуете, что темы расползаются, можно взять курс подготовки к ЕГЭ по информатике в онлайн школе. Я не за магические таблетки, но структурный план экономит нервы, особенно когда до экзамена осталось мало времени.

Главный лайфхак: переводите код на человеческий язык. Не «F вызывает F», а «если n большое, уменьшаем n и прибавляем текущую цифру». Мозгу так легче.

Ошибки, которые съедают баллы без громкого хруста

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

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

Самая частая ошибка — считать сверху вниз без подготовки. Ученик видит F(10) и сразу начинает раскрывать вызовы. Через минуту лист бумаги похож на лапшу. Лучше сначала найти нижние значения, а потом двигаться вверх.

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

Третья ошибка — забывать про несколько вызовов. Если в функции записано F(n‑1) + F(n‑1), это два вызова. Значение может быть одинаковым, но количество действий или печатей удвоится. Здесь важно внимательно читать вопрос.

Короткие правила, которые работают:

1. Всегда отмечайте базовые случаи ручкой или маркером.

1. Не меняйте условие на «примерно такое же».

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

1. Для задач с выводом рисуйте дерево или последовательность вызовов.

1. Не забывайте про ветку else.

1. После решения подставьте маленькое n для ручной проверки.

А если я панически боюсь рекурсии? Нормально. Бояться можно. Но решать всё равно придётся. Хорошая новость: после десяти разборов страх скукоживается, после двадцати он уже становится смешным.

Я советую завести отдельный лист ошибок. Не красивую тетрадь «с понедельника», а обычный список. Записали: «перепутал print и return». Через неделю повторили. Мозг любит такие короткие напоминания.

Мини-тренировка и маршрут к 90+

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

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

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

Примерный план на неделю выглядит так:

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

1. Третий — целочисленному делению и проверке на чётность.

1. Четвёртый день — рекурсии с печатью до вызова.

1. Пятый — печати после вызова и двум рекурсивным вызовам.

1. Шестой день — смешанные задачи из демоверсий и открытых банков.

1. Седьмой день — спокойный разбор ошибок без спешки.

Не гонитесь сразу за сложными номерами. Сначала добейтесь автоматизма в простых задачах. Это как в спортзале: никто не начинает с того веса, который смотрит на вас с презрением.

Когда решаете задачу, проговаривайте вслух три пункта. Где остановка? Как меняется аргумент? Что происходит при возврате? Если ответите на эти вопросы, половина решения уже готова.

Для высокого балла рекурсию нужно не просто «узнавать», а читать спокойно. Увидели функцию — сделали таблицу. Увидели print — отметили порядок вывода. Увидели две ветки — проверили условие. Никакой драмы, только аккуратность.

Не ругайте себя за временные затруднения. Я сам тупил, путаясь в F(3) на глазах у других людей, а потом привык. Рекурсия становится простой не от таланта, а от повторения и честного разбора.