Рекурсия на ЕГЭ по информатике: как решать коротко
Рекурсию на ЕГЭ по информатике решают двумя способами. Первый — руками: рисуешь дерево вызовов и идёшь по нему строго в глубину, слева направо, записывая, что печатается или возвращается. Второй — на Python: переносишь функцию из условия почти дословно и запускаешь. Ручной разбор нужен, чтобы понимать логику и проверять себя, Python — чтобы не ошибиться в длинных вычислениях. Оба способа осваиваются за несколько вечеров, а не за месяц.
Почему рекурсивная функция кажется нечитаемой
Знакомая картина: открываешь задачу, видишь функцию F, внутри которой снова вызывается F, только с другим аргументом, и мозг зависает. Вроде каждая строчка понятна, но где начинается счёт и где заканчивается — нет. Начинаешь считать в уме, на третьем вызове теряешь, откуда пришёл, и ответ получается каждый раз разный. Через десять минут хочется пропустить задачу и больше к ней не возвращаться.
Причина не в том, что рекурсия сложная. Причина в том, что её пытаются держать в голове целиком. Обычная программа идёт сверху вниз, строчка за строчкой, а рекурсивная ныряет вглубь, потом возвращается и продолжает с того места, где остановилась. Чтобы это отследить, нужно помнить стек — список незаконченных вызовов. В голове он разваливается уже на трёх-четырёх уровнях, и это нормально для любого человека, а не признак того, что ты «не технарь».
Вторая причина — в школе рекурсию часто объясняют на факториале и сразу переходят к задачам, где внутри функции два-три вызова. Факториал линейный, там нечего путать, а в экзаменационных задачах функция ветвится. Разрыв между примером и реальным заданием огромный, и кажется, что ты чего-то не понял. На самом деле не хватает одного инструмента — дерева вызовов, которое выносит стек из головы на бумагу.
Дерево вызовов: как увидеть, в каком порядке считается функция
Дерево вызовов — это схема, где каждый вызов функции записан узлом, а от него стрелками идут вызовы, которые он делает. Наверху стоит F с аргументом из условия, например F(5). Под ним — вызовы из тела функции в том порядке, в каком они написаны. Под каждым из них — их собственные вызовы, и так до тех пор, пока не дойдёшь до условия остановки, где функция больше никого не вызывает.
Главное правило чтения: функция полностью заканчивает первый вложенный вызов, со всеми его потомками, и только потом переходит ко второму. Поэтому дерево обходится не по этажам, а в глубину: спускаешься по левой ветке до самого низа, возвращаешься на шаг, идёшь в следующую ветку. Если функция печатает до вызовов, вывод появляется при входе в узел. Если после вызовов — при выходе из него, когда все потомки уже отработали.
Это и есть ответ на вопрос «в каком порядке считается». Не нужно помнить, где ты сейчас: дерево показывает это само. Рисуй его на черновике мелко, подписывай аргумент в каждом узле и отмечай галочкой узлы, которые уже прошёл. Для небольшого аргумента дерево занимает полстраницы и рисуется за пару минут, а ошибиться с ним намного сложнее, чем при счёте в уме.
Ручной разбор: что напечатает рекурсивная функция
Возьмём функцию в духе экзаменационных: def F(n) — если n > 0, то print(n), затем F(n - 2), затем F(n // 2). Нужно понять, что выведется при вызове F(5). Сначала отметь условие остановки: при n, равном нулю или меньше, функция ничего не делает и сразу возвращается. Это листья дерева, на них можно не тратить внимание. Печать стоит до вызовов, значит число выводится при входе в узел.
Входим в F(5): печатаем 5, идём в F(3). Там печатаем 3, идём в F(1). Печатаем 1, дальше F(-1) и F(0) — пустые листья. Возвращаемся в F(3) и делаем второй вызов: 3 // 2 даёт 1, снова F(1), снова печать 1. F(3) закончилась, возвращаемся в F(5) ко второму вызову: 5 // 2 даёт 2. В F(2) печатаем 2, потом F(0) пусто, потом F(1) печатает 1.
Итог — последовательность 5, 3, 1, 1, 2, 1. Если бы печать стояла после вызовов, порядок был бы другим: сначала выводились бы самые глубокие узлы. Попробуй сам переставить print в конец и пройти дерево заново — это лучшая проверка, что ты понял механику. Закрепить разбор на похожих функциях можно в бесплатном разделе /ege на Prepodoff: там теория по темам ФИПИ и тренажёры, где ответ проверяется сразу.
Числовая рекурсия: почему считать лучше снизу вверх
Второй частый вид — функция не печатает, а возвращает число. Например: F(n) = n при n < 3, иначе F(n) = F(n - 1) + 2 · F(n - 2). Просят найти F(5). Если разворачивать сверху, дерево быстро разрастается: F(5) зовёт F(4) и F(3), F(4) снова зовёт F(3), и одни и те же значения считаются по нескольку раз. На бумаге это лишняя работа и лишний шанс ошибиться.
Проще идти снизу. Запиши таблицу из двух столбцов: n и F(n). F(1) = 1, F(2) = 2 — это база из условия. Дальше F(3) = 2 + 2 · 1 = 4, F(4) = 4 + 2 · 2 = 8, F(5) = 8 + 2 · 4 = 16. Каждое следующее значение берётся из уже посчитанных, ничего не нужно держать в голове. Это та же рекурсия, только прочитанная в обратную сторону, и для ручного счёта она почти всегда надёжнее.
Внимательно смотри на условие остановки: оно может быть «n < 3», «n <= 1», «n == 1» или зависеть от чётности. Если перепутать границу, вся таблица поедет со второй строки. Отдельная ловушка — функции с ветвлением по чётности: для чётного n одна формула, для нечётного другая. Тогда в таблице полезно рядом с каждым n писать, какая ветка сработала, чтобы потом быстро найти ошибку.
Как решить рекурсию на Python за пару минут
На компьютерном экзамене не обязательно считать руками: функцию из условия можно перенести в Python почти дословно. Пишешь def F(n):, внутри if n < 3: return n, иначе return F(n - 1) + 2 * F(n - 2), а потом print(F(5)). Для функции с печатью то же самое: копируешь логику, вызываешь с нужным аргументом и смотришь вывод. Важно перенести условия и знаки один в один, без «улучшений».
Обрати внимание на деление. Если в условии целочисленное деление, в Python это //, а не /. Одиночный слеш даст дробное число, и функция уйдёт в другие ветки. С остатком так же: mod из псевдокода в Python пишется как %. Ещё один нюанс — составные условия: «n больше нуля и чётно» записывается как n > 0 and n % 2 == 0. Мелкая ошибка в знаке ломает весь ответ, поэтому перечитай перенос по строчкам.
Хорошая привычка — проверить программу на маленьком аргументе, который ты уже посчитал руками. Если Python для F(5) выдал 16, как в твоей таблице, перенос верный, и можно запускать с аргументом из задачи. Если результаты разошлись, ошибка либо в коде, либо в ручном счёте, и это лучше узнать сейчас, а не после экзамена. Так ручной разбор и Python страхуют друг друга, а не заменяют.
Типичные ошибки в задачах на рекурсию
Самая частая ошибка — обход дерева по этажам вместо обхода в глубину. Человек сначала выписывает все вызовы второго уровня, потом третьего, и порядок вывода получается неверным. Вторая — забыть, что после возврата из первого вызова функция продолжает работу и делает второй. Третья — неправильно посчитать целочисленное деление нечётных чисел, особенно когда в условии одновременно и вычитание, и деление.
Ещё одна ловушка — вопрос не про результат, а про процесс: сколько раз вызвана функция, чему равна сумма напечатанных чисел, сколько раз выведена определённая цифра. Тут легко ответить на соседний вопрос. Перед решением подчеркни, что именно спрашивают, и считай ровно это. В Python для подсчёта вызовов удобно завести счётчик снаружи функции и увеличивать его при каждом входе в неё.
И последнее — растерянность из-за непривычной записи. Функция может быть задана на псевдокоде, сразу на нескольких языках или формулами. Не пытайся сразу понять, что она «делает по смыслу»: переведи запись в простой вид «если …, то вернуть …, иначе вызвать …». Смысл функции на экзамене чаще всего и не нужен — нужен только результат конкретного вызова с конкретным аргументом.
Что делать, если Python выдаёт RecursionError или считает слишком долго
Бывает, что аргумент большой, и программа падает с ошибкой RecursionError. Это значит, что вызовы ушли слишком глубоко: у Python есть встроенное ограничение на глубину рекурсии. Его можно поднять: в начале программы пишешь import sys и sys.setrecursionlimit с заметно большим числом. Обычно этого хватает, если функция уменьшает аргумент понемногу — на единицу или на двойку за вызов.
Если программа не падает, а просто думает минутами, проблема в повторных вычислениях: одни и те же F(k) считаются снова и снова. Лечится это кэшем. Импортируй lru_cache из functools и поставь @lru_cache(None) над функцией — каждое значение посчитается один раз и запомнится. Если глубина всё равно мешает, вызывай F по очереди от маленьких n к нужному, тогда кэш заполняется постепенно.
Если и это не спасает, переходи к таблице, как в ручном счёте: заведи список, заполни базу и в цикле посчитай значения снизу вверх. Это та же идея, что на бумаге, только быстрее. А иногда задачу проще решить, заметив закономерность: выписать первые значения и увидеть, как они связаны между собой. Код в этом случае нужен, чтобы проверить догадку, а не чтобы перебрать всё подряд.
Как тренировать рекурсию, чтобы она стала обычной задачей
Рекурсия перестаёт пугать после десятка разобранных функций. Рабочий цикл тренировки такой: берёшь задачу, рисуешь дерево для маленького аргумента, считаешь руками, пишешь код, сверяешь. На первых задачах это занимает полчаса, через неделю — несколько минут. Не перескакивай сразу к коду: без ручного разбора ты не заметишь ошибку переноса, а с ним увидишь её почти сразу.
Если застрял на конкретном решении и не понимаешь, где расходится счёт, пригодится ИИ-тренер в «Моём плане» — бесплатном планировщике в Telegram. Он разбирает решения и объясняет теорию, а ещё составляет план подготовки к экзамену, чтобы рекурсия встала в него рядом с другими темами, а не висела отдельным страхом, к которому ты всё время откладываешь вернуться.
Базовую теорию и тренажёры по рекурсии и остальным темам КЕГЭ бери в бесплатном разделе /ege на Prepodoff: там материалы разложены по темам ФИПИ, есть разборы, а прогресс сохраняется в аккаунте. Решай понемногу, но регулярно — и через пару недель функция, которая вызывает сама себя, станет просто ещё одной задачей, которую ты знаешь, как разобрать.
