Ах, рекурсия! Это как тот самый кот Шрёдингера: одновременно и есть, и нет — загадка для новичков и повод для весёлых историй на программёрских кухнях.
Если вы уже успели познакомиться с её причудами в Python, узнали про ограничение глубины рекурсии (да-да, интерпретатор как строгий учитель не позволит вам уйти слишком далеко вглубь), а также освоили мемоизацию — ту самую волшебную технику, что превращает бесконечные вычисления в запоминание результатов и экономит кучу времени — то поздравляю, вы готовы к настоящему испытанию: решению 16 заданий ЕГЭ по информатике с использованием рекурсивных функций. Звучит страшно? Не беда! Это как приготовить борщ: сначала кажется сложным, а потом всё идёт на ура.
Итак, эти задания делятся по количеству рекурсивных функций в выражении.
Представьте себе: одна или две функции — словно один или два друга на вечеринке. С одним проще договориться, с двумя — начинается веселье и неожиданные повороты сюжета. Именно количество этих «друзей» определяет сложность решения.
Но не переживайте, внутри каждого типа задания очень похожи — это как разные вариации одного и того же анекдота. Мы начнём с первого типа и попробуем три способа решения: ручной метод (когда мы сами играем роль калькулятора), итеративный (представьте, что мы избавляемся от рекурсии, словно от назойливого соседа) и вариант с декоратором @lru_cache — он как шпион из шпионских фильмов: тайно запоминает результаты и возвращается к ним при необходимости.
Метод увеличения глубины рекурсии мы оставим за скобками.
Во-первых, потому что добавление одной строчки кода — это как налить чай в чашку без блюдца: вроде работает, но эстетики мало. Во-вторых, он не всегда эффективен — иногда это просто попытка засунуть слона в холодильник.
Ручной метод особенно хорош для заданий прошлых лет. Он напоминает старый добрый дедовский способ вычислений: берём функцию под микроскоп и буквально считаем все значения вручную, выявляя закономерности. Вот пример из жизни программиста-экзаменатора.
Задание 1610 звучит так: есть функция F(n), где n – целое число; если n ≥ 2025, то F(n) = n; иначе F(n) = n * 2 + F(n + 2).
Нужно найти разницу F(82) — F(81). Кажется загадочным?
Похоже на рецепт борща без списка ингредиентов!
Давайте взглянем внимательнее. У нас два пути развития событий – либо аргумент уже большой (≥2025), тогда функция просто возвращает это число; либо маленький – тогда функция вызывает себя с аргументом на 2 больше плюс удвоенное текущее значение. По сути, это похоже на ситуацию: вы хотите добраться до вершины горы (2025), но можете сделать только шаги по 2 метра вверх – каждый шаг требует усилий (умножение на 2 плюс вызов функции).
В итоге все дороги ведут к вершине.
Здесь можно вспомнить анекдот про программиста:
— Почему ты так долго сидишь над этим кодом?
— Да вот разбираюсь с рекурсией…
— А почему не просто посчитаешь вручную?
— Потому что компьютер ленивее меня!
В нашем случае ручное вычисление поможет выявить зависимость значений функции вплоть до точки 2025 — словно идти по следам муравьёв до их муравейника.
Интересно отметить ещё одну деталь: иногда в подобных заданиях встречаются выражения с делением (например, делим результат вызова функции на что-то). Тогда через пару-тройку последовательных вызовов можно упростить выражение до чистой арифметики — словно убрать посредника из сделки и сразу заключить контракт напрямую. Но здесь такой возможности нет – придётся копать глубже.