ЕГЭ по информатике 2026, задание 16: рекурсия

Задание 16 — повышенный уровень, 1 балл. Дана рекуррентная функция, нужно вычислить F(n) или сумму значений. Программу писать не обязаны, но без мемоизации рекурсия часто не заканчивается вовремя.

ФИПИ приводит ориентир: выражение вида N! / (N − 1)! не считают рекурсивным факториалом. Сначала упростите. Если программа падает по глубине стека или считает слишком долго, способ неверный, а не «нужно подождать».

Конспект

1. Выпишите базу: при каких n функция задана числом и рекурсия останавливается.

2. Упростите формулу. Сократите факториалы, заметьте период, сведите два вызова к одному.

3. Если остаётся дерево вызовов с повторами, запоминайте уже посчитанное. Это lru_cache или список.

4. База должна покрывать все ветки. Если есть F(n - 1) и F(n - 3), база нужна не в одной точке, а на нескольких подряд значениях, иначе уйдёте в отрицательные n.

5. Следите за порядком условий в программе. Сначала отсечение базы, потом рекурсивная ветка. Наоборот — бесконечный вызов.

6. Иногда спрашивают не F(n), а количество единиц при вычислении или сумму F(i) на отрезке. Тогда считайте снизу вверх циклом: это и быстрее, и прозрачнее.

Цикл снизу вверх предпочтительнее рекурсии, если зависимость только от меньших аргументов.

Шаблон на Python

from functools import lru_cache

@lru_cache(None)
def f(n):
    if n < 3:
        return n
    if n % 2 == 0:
        return f(n - 1) + 2 * n
    return f(n - 2) + n

print(f(20))

# тот же счёт циклом, если каждый F зависит только от меньших
N = 20
F = [0] * (N + 1)
for n in range(N + 1):
    if n < 3:
        F[n] = n
    elif n % 2 == 0:
        F[n] = F[n - 1] + 2 * n
    else:
        F[n] = F[n - 2] + n
print(F[N], sum(F))

Если n большое, а ветки вычитают единицу, глубина рекурсии равна n. Тогда либо цикл, либо sys.setrecursionlimit. Лимит не лечит экспоненциальное дерево без кэша: сначала кэш, потом лимит.

Типичные ошибки

• Нет условия остановки для всех веток.
• Кэш забыт, и одинаковые F(k) считаются тысячи раз.
• Упрощение n! / (n-1)! = n не замечено, программа считает факториал большого n.
• Сумма собрана от 1 до n без тех n, где функция не определена по условию.