В задании 16 ЕГЭ 2025 года требуется вычислить значение функции, заданной рекуррентным выражением. В этом выражении формула для нахождения следующего элемента последовательности зависит от определённых условий, которым должен удовлетворять аргумент функции.
Скачать теория: Скачать
Смотреть онлайн
Пример ручного решения из демоверсии-2020
При вызове F(5) алгоритм сначала выведет значение 5, после чего выполнит вызов F(5 // 2) = F(2). Для F(2) выведет 2 и передаст управление вверх (продолжит выполнять F(5)). Выполнится вызов F(4) – будет выведено 4 и вызвана функция F(4 // 2) = F(2), которая выведет 2 и передаст управление обратно F(4). Вызывается F(3), в ходе выполнения которой печатается 3 и вызывается F(3//2) = F(1). Печатается 1 и вызывается F(3-1) = F(2) – печатается 2 и управление передается на уровень выше, после чего завершается выполнение F(3), далее F(4) и F(5). Также данное рассуждение можно представить в виде изображения
Ответ: 5242312
Пример программного решения из демоверсии-2020 Просто перепишем код из задания и запустим его.
def F(n):
print(n, end=»)
if n >= 3:
F(n // 2)
F(n — 1)
print(F(5))
>> 5242312
Как можно заметить, ничего сложного. Однако, могут быть постановки, где придется подумать больше. Таковые были и на экзамене. Поэтому рассмотрим методы детальнее и попробуем максимально обезопасить себя от ловушек на экзамене. Также становится понятно, почему ФИПИ ушел от постановки задачи в виде программы – при такой постановке задача сдающего сводится к переписыванию кода и его запуску. Однако, существует ряд задач, которые при подобной предполагают либо существенное изменение кода, либо вообще аналитическое решение (из-за невозможности в приемлемое время ответить на вопрос задачи). Аналитический подход В первую очередь необходимо ввести несколько определений. Выход из рекурсии – определение значения рекурсивной функции (рекуррентного выражения) без повторного обращения к этой самой функции. В задании из демоверсии-2024 это было выражение F(n) = n.
Глубина рекурсии – максимальное количество вычисляемых в определенный момент времени значений функции или максимальное количество вложенных вызовов рекурсивной функции. Так, например, при вызове F(2022) из условия демо-2024 нужно было вычислить F(2023) для этого вычислить F(2024), значение которой уже определялось без следующего шага рекурсии. Таким образом глубина рекурсии была 3 (пока не определилось значение F(2024), нельзя было определить значение F(2023), а без него нельзя было определить значение F(2022)). Шаг рекурсии (рекурсивный вызов) – вложенный вызов функцией самой себя. Так запись F(n) = n ⸱ F(n+1) осуществляет шаг рекурсии. Принято считать, что рекурсия «шагает» вглубь. Далее мы ответим на вопрос почему.
Вы можете создать экзаменационный типовой вариант ВПР, ЕГЭ и ОГЭ на нашем сайте