2

введите сюда описание изображения

def recursion(n):
    return 1 if n == 1 else 1 + recursion(n - recursion(recursion(n - 1)))
 
print(recursion(int(input())))

Я написал код но он слишком долгий, можно как нибудь его ускорить?

1

2 ответа 2

4

Если вы переиспользуете функцию, то можно кэшировать результат с помощью стандартной библиотеки 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)))
1
  • 1
    помогло, спасибо большое
    – Derzh
    30 янв 2021 в 16:16
2

можно попробовать самому реализовать 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)))
3
  • 1
    Только это не lru_cache, ну, вернее, это аналог неограниченного кэша, такого же, впрочем, как использован за счёт параметра в другом ответе. Просто строго говоря, LRU cache должен "помнить" не все элементы, а только недавно использованные.
    – CrazyElf
    30 янв 2021 в 17:47
  • @CrazyElf это просто жалкая пародия на lru_cache
    – Danis
    30 янв 2021 в 18:11
  • 2
    Короче, это кэш, но не LRU, извиняюсь за педантизм ))
    – CrazyElf
    30 янв 2021 в 18:40

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.