№ 1612. Типовые варианты - ЕГЭ по информатике

Алгоритм вычисления значения функции $F(n)$ , где $n$ – целое неотрицательное число, задан следующими соотношениями:
$F(n)=1$ при $n < 3$ ;
$F(n)= F(n-1) - F(n-2)$ , если $n > 2$ и при этом $n$ нечётно;
$F(n)= \sum_{i=1}^{n-1} F(i)$ , если $n > 2$ и при этом $n$ чётно
Чему равно значение функции $F(39)$ ?

Ответ
Python

41518080

from functools import lru_cache

@lru_cache()
def f(n):
    if n > 2 and n % 2:
        return f(n-1) - f(n-2)
    elif n > 2 and (n % 2 == 0):
        return sum(f(i) for i in range(1, n))
    elif 0 < n < 3:
        return 1

for i in range(0, 39):
    f(i)
    
print(f(39))