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

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

Номер и тему сверяйте по демоверсии 2027 года: статья описывает устройство задания, не пересказывая конкретный вариант. Рекурсия относится к тем заданиям, где важно выбрать способ до начала решения, потому что неверный выбор съедает заметную часть времени впустую. Общая карта первой части есть в статье про первую часть ЕГЭ по информатике, а язык, на котором вы пишете, определяет, какие из трудностей ниже вас коснутся: об этом сравнение Python и C++.

Как читать определение

В любом определении есть базовый случай (значение при единице или при единице и двойке) и шаг, выражающий значение через предыдущие. Иногда шаг разбит на ветви по условию: одно правило для чётных n, другое для нечётных. Определение — математическое соотношение, и команды компьютеру в нём нет; это снимает много лишних вопросов: никто ничего не вызывает, просто значение при n связано со значениями при меньших n.

На экзамене порядок такой. Сначала прочитать последнюю строку условия и понять, что требуется: значение или число вызовов. Потом выписать пять-шесть первых значений вручную. Потом либо найти закономерность и подтвердить её подстановкой, либо переходить к программе. Менять порядок не стоит: ученики, которые сразу открывают редактор, нередко получают число, но не могут объяснить себе, правдоподобно ли оно, и вводят его на веру.

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

Сначала малые n

Возьмите функцию: F(1) = 1 и F(n) = n · F(n − 1) при n больше единицы. Это факториал, и если просят отношение значения при 2026 к значению при 2024, вычислять факториалы не нужно: числитель раскладывается в 2026 · 2025 · значение при 2024, значение сокращается, остаётся 2026 · 2025, то есть 4102650. Программа здесь без толку, она бы создавала число в несколько тысяч знаков ради двух множителей.

Другой пример. Теперь функция иного вида: F(1) = 1 и F(n) = F(n − 1) + 2n − 1 при n больше единицы. Выпишите пять значений: 1, 4, 9, 16, 25. Закономерность видна сразу, это квадраты, и разность значений при 2027 и при 2025 равна 2027 в квадрате минус 2025 в квадрате, то есть 2 · 4052, получается 8104. Найденную формулу проверяют подстановкой в определение: если F(n − 1) равно (n − 1) в квадрате, то прибавление 2n − 1 даёт ровно n в квадрате, и закономерность подтверждена не только на пяти значениях, но и вообще. Без этой проверки она остаётся догадкой.

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

Что ломается в Python

Когда закономерности нет, пишется функция, повторяющая определение слово в слово, и дальше её подстерегают четыре беды:

• Глубина. Интерпретатор по умолчанию разрешает около тысячи вложенных вызовов, и для n в две тысячи программа падает с ошибкой превышения глубины. Лечится одной строкой в начале: sys.setrecursionlimit(10000) после подключения модуля sys.
• Повторные вызовы. Если значение при n зависит от двух предыдущих, как у чисел Фибоначчи, функция без запоминания считает одни и те же значения многократно, и при n, равном сорока, вызовов порядка двухсот миллионов. Лечится запоминанием: перед определением функции ставится @lru_cache(None) из модуля functools.
• Деление. Обычная косая черта в Python возвращает вещественное число, а вещественное число не может быть больше примерно 10 в 308 степени. Отношение двух огромных целых числа поэтому падает с ошибкой переполнения, а если не падает, то теряет точность. Для точного деления нацело нужна двойная косая черта, и результат стоит сверить с остатком.
• Забытая остановка. Если в программе нет базового случая или граница в нём стоит неверно, вызовы уходят вглубь без конца, и ошибка выглядит так же, как в первой беде. Поднятие предела здесь не поможет, нужно перечитать базовый случай.

Каждая из четырёх бед лечится за секунды, но, чтобы не терять на них время, надо знать признак. Падение с длинным сообщением про глубину — первая или четвёртая; отличить их можно, посмотрев, велико ли n: на пяти вызовах до предела тысячи не дойти. Программа, которая «думает» и не выдаёт ответа, — вторая. Сообщение про результат деления, слишком большой для вещественного числа, — третья.

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

Цикл вместо рекурсии

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

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

Язык тоже играет роль. В C++ целое число стандартного размера кончается раньше, чем кончается терпение: факториал уже на двадцать первом члене не помещается в 64 разряда, и значение молча портится. Задачи на отношение значений в таком случае приходится решать руками, сократив общую часть, и это ещё один довод в пользу той самой привычки искать закономерность до программы.

Ветвление по чётности

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

Возьмите функцию F(1) = 1, F(n) = F(n / 2) при чётном n и F(n) = F(n − 1) + 1 при нечётном. Первые значения: F(2) = 1, F(3) = 2, F(4) = 1, F(5) = 2, F(6) = 2, F(7) = 3. Это число единиц в двоичной записи n, и объясняется оно просто: деление пополам отбрасывает последний нуль, а вычитание единицы из нечётного числа убирает последнюю единицу и добавляет к счёту одну. Для числа 1023, которое в двоичной записи состоит из десяти единиц, ответ равен десяти, и программа не нужна вовсе. Связь с двоичной записью знакома тем, кто разбирал системы счисления в задании 14: рекурсивное определение там и тут описывает одно и то же поведение с разных сторон.

Откуда берётся уверенность

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

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

Если рекурсия не поддаётся

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

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

Начать поиск:

• репетиторы по информатике для подготовки к ЕГЭ
• все репетиторы для подготовки к ЕГЭ

Следующее по теме задание, где снова нужны числа и аккуратность с форматом ответа, — задание 22 про процессы и ресурсы.

Вопросы и ответы

Обязательно ли знать, что такое стек вызовов? Нет. Достаточно помнить, что у вложенных вызовов есть предел глубины и что его можно поднять.

Можно ли обойтись вообще без программы? Иногда да, если закономерность видна, как в примере с отношением факториалов. Но заранее это не определить, и безопаснее уметь и то и другое.

Почему программа, которая работала на n, равном тридцати, зависает на сорока? Там экспоненциальный рост числа вызовов, потому что значения при меньших n пересчитываются снова и снова. Запоминание значений или цикл вперёд убирают проблему целиком: программа, зависавшая минутами, отрабатывает мгновенно, потому что каждое значение считается ровно один раз. Это самая частая причина, по которой решение «работает на примере, но не на данных».

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