16.01 Одна функция

Рекурсивное решение

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью . Внутри функции используем условный оператор , чтобы задать ветвление. Для используем явную формулу . Для рекуррентно считаем по . Нужно перебрать все целые из отрезка и посчитать, для скольких кратно . Чтобы рекурсия работала быстро и не упиралась в глубину, увеличим лимит рекурсии и запомним уже вычисленные значения с помощью кеширования.

from functools import lru_cache
import sys

# Увеличиваем максимально допустимую глубину рекурсии
sys.setrecursionlimit(10000000)

@lru_cache(None)
def f(n):
    # Ветка: n > 10 — используем явную формулу
    if n > 10:
        return 2 ** n + 3
    # Иначе: n <= 10 — рекуррентная формула
    else:
        return f(n + 2) + 2 * f(n + 1)

# Считаем, для скольких n из [-1000; 1000] значение F(n) кратно 3
ans = 0
for i in range(-1000, 1001):
    if f(i) % 3 == 0:
        ans += 1

print(ans)