Задание 16 ЕГЭ: факториальная рекурсия: значение выражения

Факториальная рекурсия: значение выражения. Тема номера — рекурсивные функции. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

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

F(n) = 1 при n ≤ 4;
F(n) = (n + 3) × F(n − 1), если n > 4.

Чему равно значение выражения (F(4994) − 8 × F(4993)) / F(4992)?

Решение

По определению F(4994) = 4997 · F(4993) и F(4993) = 4996 · F(4992), значит, F(4994) = 4997 · 4996 · F(4992). Делим числитель на F(4992): 4997 · 4996 − 8 · 4996 = 4996 · 4989 = 24 925 044.

Проверим программой. Рекурсия глубиной в тысячи вызовов переполнит стек (Python выдаст RecursionError даже с увеличенным sys.setrecursionlimit), поэтому значения F считаем по той же формуле в цикле — от меньших n к большим. Числа огромные, но Python считает их точно, а все деления здесь нацело.

F = {}
for n in range(1, 4995):
    if n < 5:
        F[n] = 1
    else:
        F[n] = (n + 3) * F[n - 1]

print((F[4994] - 8 * F[4993]) // F[4992])

Ответ: 24925044.

Решить такую задачу — новый вариант с проверкой