Рубрики
ЕГЭ Информатика

ЕГЭ № 16. Анализ рекурсивных подпрограмм

Разберём задачу № 16 из Демо варианта – 2023.

Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(n) = 1, n = 1
F(n) = n × F(n-1), n > 1

Чему равно значение выражения F(2023) / F(2020)?

Казалось бы, просится «наивное» решение в три строчки «в лоб»:

def f(n):
    return 1 if n == 1 else n * f(n - 1)


print(f(2023) / f(2020))

Однако этот код закономерно выдаст ошибку:

builtins.RecursionError: maximum recursion depth exceeded in comparison

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

Такие задания предполагают в первую очередь понимания того, как работает рекурсивная программа. «Вооружившись» этим пониманием, посмотрим на задачу аналитически, буквально развернув первые несколько витков рекурсивной функции.

{F(2023) \over F(2020)} = \\ = {2023 × F(2022) \over F(2020)} = {2023 × 2022 ×F(2021) \over F(2020)} = \\
= {2023 × 2022 × 2021 × F(2020) \over F(2020)} = \\ = 2023×2022×2021 
= 8266912626

Мы получили ответ буквально устно (да, нужно было выполнить два умножения — благо, возможность выполнять вычисления во время КЕГЭ доступна, как минимум, на калькуляторе или в консоли Python).

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

Видоизменим программу следующим образом:

import sys


def f(n):
    return 1 if n == 1 else n * f(n - 1)


sys.setrecursionlimit(2500)
print(f(2023) / f(2020))

Программа выдаст верный результат: 8266912626.0 (очевидно, в ответ мы должны записать целочисленное значение).

Попрактиковаться можно, решая задачи из этого раздела.

Автор: Дмитрий Серженко

Заместитель директора, учитель информатики, педагог дополнительного образования школы № 509