Задание №16 — Рекурсия

Решение:

Число 43 нечётное, поэтому работает правило $F(n) = 3n + F(n-2)$: аргумент уменьшается на 2 и остаётся нечётным. Значит вся цепочка идёт только по нечётным числам, вплоть до $F(1) = 1$, а правило для чётных $n$ не используется.

$$F(43) = 3 \cdot 43 + F(41) = 3 \cdot 43 + 3 \cdot 41 + F(39) = \dots = 3 \cdot (43 + 41 + \dots + 3) + F(1).$$

В сумме $3 + 5 + \dots + 43$ ровно 21 слагаемое, её значение равно $\frac{(3 + 43) \cdot 21}{2} = 23 \cdot 21 = 483$.

Итого $F(43) = 3 \cdot 483 + 1 = 1449 + 1 = 1450$.

from functools import lru_cache

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

print(F(43))   # 1450

Ответ: 1450