Задание 16 ЕГЭ

Pascal abc.net:
function f(n: integer): integer;
begin
  if n<=2 then f:=2 else
    f:=f(n-1) + 3*f(n-2);
end;
begin
  print(f(5))
end.
------------------------------------------------------------------------------------------------------------------
Python:
### Есть несколько случаев, когда надо применять различные модули для реализации кода.
1) Если не хватает глубины рекурсии, то
import sys
sys.setrecursionlimit(10000) --> устанавливаем глубину рекурсии, то есть мы могли уходить вглубь больше.
2) Если нужно запоминать множество значений, то
from functools import lru_cache
@lru_cache(None) --> данная функция создает словарик, который сохраняет значения для опр n.
Полезно, когда много обращений к прошлым значениям. Повышает производительность системы, так как заново не надо считать.
Обязательно должны его заполнить, в ином случае толку не будет.
Пример:
from functools import lru_cache
@lru_cache(None)
def f(n):
    if n == 1: return 1
    if n > 1 and n % 2 == 0: return n // 2 + f(n-1)
    if n > 1 and n % 2 != 0: return n + f(n-2)

for i in range(1,10000):
    f(i)

print(f(10000) - f(9993))
P.S если в задании несколько функций, то к каждой накладываем кэш. 2 функции, значит 2 кэша.