Задание 16 ЕГЭ: рекурсия со сложением

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

Пример

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

F(n) = 3 при n ≤ 16;
F(n) = F(n − 2) + 2n, если n > 16.

Чему равно значение выражения F(2954) − F(2916)?

Решение

Раскроем F(2954) по определению 19 раз: каждый шаг уменьшает аргумент на 2 и добавляет 2n. После 19 шагов получится F(2916), поэтому разность — это сумма 19 слагаемых при n = 2954, 2952, …, 2918: 111 568. Вычислять сами F(2954) и F(2916) не нужно, а рекурсия глубиной в тысячи вызовов в Python падает.

Проверим программой: значения считаем в цикле, без глубокой рекурсии.

f = {}
for n in range(1, 2954 + 1):
    f[n] = 3 if n <= 16 else f[n - 2] + 2 * n + (0)
print(f[2954] - f[2916])

Ответ: 111568.

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