Разберём задачу № 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 (очевидно, в ответ мы должны записать целочисленное значение).
Попрактиковаться можно, решая задачи из этого раздела.
