5 Способ 2 — таблица (без рекурсии)

Способ 2 — таблица (без рекурсии)

Заводим массив и заполняем его от базы по формуле. Здесь никакой глубины рекурсии нет вообще — способ железобетонный.

f = [0] * 2024
f[1] = 3                            # база
for n in range(2, 2024):           # заполняем по порядку
    f[n] = n + 2 + f[n - 1]         # та же формула
print(f[2023] - f[2021])           # 4049

Если база для больших n (считаем вниз), заполняем массив в обратную сторону:

f = [0] * 2028
for n in range(2027, -1, -1):      # идём от больших n к маленьким
    if n >= 2025: f[n] = n          # база
    else: f[n] = n + 3 + f[n + 3]    # формула
print(f[2018] - f[2022])

Пример: разбор по шагам

Условие

F(n) = 3 при n = 1; F(n) = n + 2 + F(n − 1) при n > 1. Чему равно F(2023) − F(2021)?

Переносим базу и формулу в любой из способов:

f = [0] * 2024
f[1] = 3
for n in range(2, 2024):
    f[n] = n + 2 + f[n - 1]
print(f[2023] - f[2021])           # 4049

Ответ: 4049

💡 Две функции F и G

Иногда F выражается через вспомогательную G (например, F(n) = 2*G(n-3) + 8, а G задана своей рекуррентой). Тогда сначала посчитай таблицу для G, а F — по её значениям. Схема та же: база → формула → таблица.