def recursion(n):
return 1 if n == 1 else 1 + recursion(n - recursion(recursion(n - 1)))
print(recursion(int(input())))
Я написал код но он слишком долгий, можно как нибудь его ускорить?
Stack Overflow на русском — это сайт вопросов и ответов для программистов. Присоединяйтесь! Регистрация займёт не больше минуты.
Присоединиться к сообществуЕсли вы переиспользуете функцию, то можно кэшировать результат с помощью стандартной библиотеки python
from functools import lru_cache
@lru_cache(maxsize=None)
def recursion(n):
return 1 if n == 1 else 1 + recursion(n - recursion(recursion(n - 1)))
можно попробовать самому реализовать lru_cache
def lru_cache(func):
dict_ = {}
def wrapper(n):
if n not in dict_:
dict_[n] = func(n)
return dict_[n]
return wrapper
@lru_cache
def recursion(n):
return 1 if n == 1 else 1 + recursion(n - recursion(recursion(n - 1)))
lru_cache
, ну, вернее, это аналог неограниченного кэша, такого же, впрочем, как использован за счёт параметра в другом ответе. Просто строго говоря, LRU cache
должен "помнить" не все элементы, а только недавно использованные.